oj.uz

Submission #706145

# Submission time Handle Problem Language Result Execution time Memory
706145 2023-03-06T01:21:20 Z LittleCube Road Construction (JOI21_road_construction) C++14
100 / 100
 8968 ms 77384 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], pp[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, int, int>> v;
    vector<ll> vy;
    v.reserve(3 * N);
    vy.reserve(3 * N + 1);
    ll res = 0;
    for (int i = 1; i <= N; i++)
    {
        vy.emplace_back(pp[i].S - L);
        vy.emplace_back(pp[i].S);
        vy.emplace_back(pp[i].S + L);
    }
    vy.emplace_back(-1e12);
    sort(vy.begin(), vy.end());
    vy.resize(unique(vy.begin(), vy.end()) - vy.begin());
    
    for (int i = 1; i <= N; i++)
    {
        ll x = pp[i].F, y = pp[i].S, 
        l = lower_bound(vy.begin(), vy.end(), y - L) - vy.begin(),
        m = lower_bound(vy.begin(), vy.end(), y) - vy.begin(),
        r = lower_bound(vy.begin(), vy.end(), y + L) - vy.begin();
        
        v.emplace_back(make_tuple(x - L, -1, m, 0));
        v.emplace_back(make_tuple(x, 0, l, r));
        v.emplace_back(make_tuple(x + L, 1, m, 0));
    }
    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(l, 1);
        else if (t == 1)
            modify(l, -1);
        else if (t == 0)
            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;
    for (int i = 1; i <= N; i++)
        pp[i] = pll(p[i].F + p[i].S, 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());
    while (ans.size() < K)
        ans.emplace_back(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:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp:121: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]
  121 |     while (ans.size() < K)
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5180 KB Output is correct
2 Correct 65 ms 5184 KB Output is correct
3 Correct 56 ms 5136 KB Output is correct
4 Correct 56 ms 5148 KB Output is correct
5 Correct 61 ms 4036 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 8047 ms 72592 KB Output is correct
2 Correct 8048 ms 72536 KB Output is correct
3 Correct 51 ms 5008 KB Output is correct
4 Correct 7870 ms 72076 KB Output is correct
5 Correct 8000 ms 71736 KB Output is correct
6 Correct 7999 ms 71456 KB Output is correct
7 Correct 8058 ms 70732 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8322 ms 70292 KB Output is correct
2 Correct 8268 ms 70232 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 8012 ms 70228 KB Output is correct
5 Correct 6137 ms 70272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8322 ms 70292 KB Output is correct
2 Correct 8268 ms 70232 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 8012 ms 70228 KB Output is correct
5 Correct 6137 ms 70272 KB Output is correct
6 Correct 8183 ms 70292 KB Output is correct
7 Correct 8363 ms 70224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 8179 ms 70228 KB Output is correct
11 Correct 7953 ms 70228 KB Output is correct
12 Correct 6112 ms 70232 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5180 KB Output is correct
2 Correct 65 ms 5184 KB Output is correct
3 Correct 56 ms 5136 KB Output is correct
4 Correct 56 ms 5148 KB Output is correct
5 Correct 61 ms 4036 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 3246 ms 31556 KB Output is correct
8 Correct 3215 ms 31556 KB Output is correct
9 Correct 57 ms 5244 KB Output is correct
10 Correct 3003 ms 31560 KB Output is correct
11 Correct 2929 ms 31560 KB Output is correct
12 Correct 2208 ms 31564 KB Output is correct
13 Correct 2356 ms 31560 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5180 KB Output is correct
2 Correct 65 ms 5184 KB Output is correct
3 Correct 56 ms 5136 KB Output is correct
4 Correct 56 ms 5148 KB Output is correct
5 Correct 61 ms 4036 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 8047 ms 72592 KB Output is correct
8 Correct 8048 ms 72536 KB Output is correct
9 Correct 51 ms 5008 KB Output is correct
10 Correct 7870 ms 72076 KB Output is correct
11 Correct 8000 ms 71736 KB Output is correct
12 Correct 7999 ms 71456 KB Output is correct
13 Correct 8058 ms 70732 KB Output is correct
14 Correct 8322 ms 70292 KB Output is correct
15 Correct 8268 ms 70232 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 8012 ms 70228 KB Output is correct
18 Correct 6137 ms 70272 KB Output is correct
19 Correct 8183 ms 70292 KB Output is correct
20 Correct 8363 ms 70224 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 8179 ms 70228 KB Output is correct
24 Correct 7953 ms 70228 KB Output is correct
25 Correct 6112 ms 70232 KB Output is correct
26 Correct 3246 ms 31556 KB Output is correct
27 Correct 3215 ms 31556 KB Output is correct
28 Correct 57 ms 5244 KB Output is correct
29 Correct 3003 ms 31560 KB Output is correct
30 Correct 2929 ms 31560 KB Output is correct
31 Correct 2208 ms 31564 KB Output is correct
32 Correct 2356 ms 31560 KB Output is correct
33 Correct 8940 ms 72200 KB Output is correct
34 Correct 8968 ms 72272 KB Output is correct
35 Correct 8209 ms 76584 KB Output is correct
36 Correct 6058 ms 77384 KB Output is correct
37 Correct 6046 ms 77304 KB Output is correct
38 Correct 6401 ms 76068 KB Output is correct