oj.uz

Submission #706133

# Submission time Handle Problem Language Result Execution time Memory
706133 2023-03-06T01:02:11 Z LittleCube Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 71576 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll N, K, bit[750005];
pll p[250005];

void modify(int pos, int val)
{
    for (int i = pos; i <= 3 * N; i += (i & -i))
        bit[i] += val;
}

ll query(int pos)
{
    ll val = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        val += bit[i];
    return val;
}

ll calc(ll L)
{
    vector<tuple<ll, int, ll, ll>> v;
    vector<ll> vy;
    ll res = 0;
    for (int i = 1; i <= N; i++)
    {
        ll x = p[i].F + p[i].S, y = p[i].F - p[i].S;
        v.emplace_back(make_tuple(x - L, -1, y, 0));
        v.emplace_back(make_tuple(x, 0, y - L, y + L));
        v.emplace_back(make_tuple(x + L, 1, y, 0));
        vy.emplace_back(y - L);
        vy.emplace_back(y);
        vy.emplace_back(y + L);
    }
    vy.emplace_back(-1e12);
    sort(vy.begin(), vy.end());
    vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
    sort(v.begin(), v.end());
    for (int i = 1; i <= 3 * N; i++)
        bit[i] = 0;
    for (auto [x, t, l, r] : v)
    {
        if (t == -1)
            modify(lower_bound(vy.begin(), vy.end(), l) - vy.begin(), 1);
        if (t == 1)
            modify(lower_bound(vy.begin(), vy.end(), l) - vy.begin(), -1);
        if (t == 0)
        {
            int L = lower_bound(vy.begin(), vy.end(), l) - vy.begin(), R = lower_bound(vy.begin(), vy.end(), r) - vy.begin();
            res += query(R) - query(L - 1) - 1;
        }
    }
    return res / 2;
}

signed main()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> p[i].F >> p[i].S;
    ll L = 1, R = 4'000'000'000;
    while (L < R)
    {
        ll mid = (L + R) / 2;
        if (calc(mid) < K)
            L = mid + 1;
        else
            R = mid;
    }
    L--;

    vector<tuple<ll, int, ll, ll>> v;
    multiset<ll> ans;
    set<pll> st;

    for (int i = 1; i <= N; i++)
    {
        ll x = p[i].F + p[i].S, y = p[i].F - p[i].S;
        v.emplace_back(make_tuple(x - L, -i, y, 0));
        v.emplace_back(make_tuple(x, i, y - L, y + L));
        v.emplace_back(make_tuple(x + L, i + N, y, 0));
    }
    sort(v.begin(), v.end());
    for (auto [x, t, l, r] : v)
    {
        if (t < 0)
            st.insert(pll(l, -t));
        else if (t > N)
            st.erase(pll(l, t - N));
        else 
        {
            auto lter = st.lower_bound(pll(l, 0)), rter = st.upper_bound(pll(r, N + 1));

            while(lter != rter)
            {
                ll i = lter->S;
                if(i < t)
                    ans.insert(abs(p[t].F - p[i].F) + abs(p[t].S - p[i].S));
                ++lter;
            }
        }
    }
    while(ans.size() < K)
        ans.insert(R);
    for(ll i : ans)
        cout << i << '\n';
}

Compilation message

road_construction.cpp: In function 'long long int calc(long long int)':
road_construction.cpp:46:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:89:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp:108:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  108 |     while(ans.size() < K)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 14780 KB Output is correct
2 Correct 183 ms 14740 KB Output is correct
3 Correct 172 ms 14820 KB Output is correct
4 Correct 183 ms 14768 KB Output is correct
5 Correct 182 ms 13820 KB Output is correct
6 Correct 16 ms 612 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7057 ms 69600 KB Output is correct
2 Correct 6963 ms 69652 KB Output is correct
3 Correct 154 ms 14656 KB Output is correct
4 Correct 6770 ms 69688 KB Output is correct
5 Correct 6730 ms 69588 KB Output is correct
6 Correct 6751 ms 69704 KB Output is correct
7 Correct 6778 ms 69864 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10077 ms 71576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10077 ms 71576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 14780 KB Output is correct
2 Correct 183 ms 14740 KB Output is correct
3 Correct 172 ms 14820 KB Output is correct
4 Correct 183 ms 14768 KB Output is correct
5 Correct 182 ms 13820 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 4291 ms 34040 KB Output is correct
8 Correct 4104 ms 34212 KB Output is correct
9 Correct 154 ms 14760 KB Output is correct
10 Correct 3914 ms 33348 KB Output is correct
11 Correct 3718 ms 33320 KB Output is correct
12 Correct 2599 ms 34168 KB Output is correct
13 Correct 2746 ms 32780 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 14780 KB Output is correct
2 Correct 183 ms 14740 KB Output is correct
3 Correct 172 ms 14820 KB Output is correct
4 Correct 183 ms 14768 KB Output is correct
5 Correct 182 ms 13820 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 7057 ms 69600 KB Output is correct
8 Correct 6963 ms 69652 KB Output is correct
9 Correct 154 ms 14656 KB Output is correct
10 Correct 6770 ms 69688 KB Output is correct
11 Correct 6730 ms 69588 KB Output is correct
12 Correct 6751 ms 69704 KB Output is correct
13 Correct 6778 ms 69864 KB Output is correct
14 Execution timed out 10077 ms 71576 KB Time limit exceeded
15 Halted 0 ms 0 KB -