oj.uz

Submission #706134

# Submission time Handle Problem Language Result Execution time Memory
706134 2023-03-06T01:07:53 Z LittleCube Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 69288 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#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;
    vector<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.emplace_back(abs(p[t].F - p[i].F) + abs(p[t].S - p[i].S));
                ++lter;
            }
        }
    }
    sort(ans.begin(), ans.end());
    assert(ans.size() < K);
    while(ans.size() < K)
        ans.emplace_back(R);
    for(ll i : ans)
        cout << i << '\n';
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from road_construction.cpp:2:
road_construction.cpp: In function 'int main()':
road_construction.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  110 |     assert(ans.size() < K);
      |            ~~~~~~~~~~~^~~
road_construction.cpp:111:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  111 |     while(ans.size() < K)
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5216 KB Output is correct
2 Correct 69 ms 5276 KB Output is correct
3 Correct 61 ms 5192 KB Output is correct
4 Correct 64 ms 5404 KB Output is correct
5 Correct 64 ms 4088 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 7412 ms 68748 KB Output is correct
2 Correct 7324 ms 68824 KB Output is correct
3 Correct 54 ms 5220 KB Output is correct
4 Correct 7363 ms 68760 KB Output is correct
5 Correct 7198 ms 68900 KB Output is correct
6 Correct 7211 ms 69288 KB Output is correct
7 Correct 7288 ms 68760 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10092 ms 69012 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 10092 ms 69012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5216 KB Output is correct
2 Correct 69 ms 5276 KB Output is correct
3 Correct 61 ms 5192 KB Output is correct
4 Correct 64 ms 5404 KB Output is correct
5 Correct 64 ms 4088 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 4155 ms 32200 KB Output is correct
8 Correct 4253 ms 32084 KB Output is correct
9 Correct 58 ms 5300 KB Output is correct
10 Correct 3909 ms 31492 KB Output is correct
11 Correct 3880 ms 31300 KB Output is correct
12 Correct 2871 ms 32464 KB Output is correct
13 Correct 3036 ms 31004 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5216 KB Output is correct
2 Correct 69 ms 5276 KB Output is correct
3 Correct 61 ms 5192 KB Output is correct
4 Correct 64 ms 5404 KB Output is correct
5 Correct 64 ms 4088 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 7412 ms 68748 KB Output is correct
8 Correct 7324 ms 68824 KB Output is correct
9 Correct 54 ms 5220 KB Output is correct
10 Correct 7363 ms 68760 KB Output is correct
11 Correct 7198 ms 68900 KB Output is correct
12 Correct 7211 ms 69288 KB Output is correct
13 Correct 7288 ms 68760 KB Output is correct
14 Execution timed out 10092 ms 69012 KB Time limit exceeded
15 Halted 0 ms 0 KB -