oj.uz

Submission #706142

# Submission time Handle Problem Language Result Execution time Memory
706142 2023-03-06T01:17:47 Z LittleCube Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 77420 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;
    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:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp: In function 'int main()':
road_construction.cpp:100:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for (auto [x, t, l, r] : v)
      |               ^
road_construction.cpp:120: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]
  120 |     while (ans.size() < K)
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5196 KB Output is correct
2 Correct 71 ms 5100 KB Output is correct
3 Correct 60 ms 5132 KB Output is correct
4 Correct 60 ms 5252 KB Output is correct
5 Correct 64 ms 4040 KB Output is correct
6 Correct 17 ms 596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8877 ms 72996 KB Output is correct
2 Correct 8756 ms 72716 KB Output is correct
3 Correct 56 ms 5032 KB Output is correct
4 Correct 9129 ms 72472 KB Output is correct
5 Correct 9087 ms 73372 KB Output is correct
6 Correct 8889 ms 73472 KB Output is correct
7 Correct 8929 ms 72804 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9257 ms 72284 KB Output is correct
2 Correct 9227 ms 75436 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 8845 ms 73204 KB Output is correct
5 Correct 6842 ms 75820 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9257 ms 72284 KB Output is correct
2 Correct 9227 ms 75436 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 8845 ms 73204 KB Output is correct
5 Correct 6842 ms 75820 KB Output is correct
6 Correct 9229 ms 75296 KB Output is correct
7 Correct 9197 ms 75376 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 8958 ms 75296 KB Output is correct
11 Correct 8840 ms 73108 KB Output is correct
12 Correct 6878 ms 75624 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5196 KB Output is correct
2 Correct 71 ms 5100 KB Output is correct
3 Correct 60 ms 5132 KB Output is correct
4 Correct 60 ms 5252 KB Output is correct
5 Correct 64 ms 4040 KB Output is correct
6 Correct 17 ms 596 KB Output is correct
7 Correct 3576 ms 34708 KB Output is correct
8 Correct 3582 ms 34672 KB Output is correct
9 Correct 58 ms 5280 KB Output is correct
10 Correct 3402 ms 33964 KB Output is correct
11 Correct 3292 ms 33940 KB Output is correct
12 Correct 2514 ms 34552 KB Output is correct
13 Correct 2682 ms 32916 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5196 KB Output is correct
2 Correct 71 ms 5100 KB Output is correct
3 Correct 60 ms 5132 KB Output is correct
4 Correct 60 ms 5252 KB Output is correct
5 Correct 64 ms 4040 KB Output is correct
6 Correct 17 ms 596 KB Output is correct
7 Correct 8877 ms 72996 KB Output is correct
8 Correct 8756 ms 72716 KB Output is correct
9 Correct 56 ms 5032 KB Output is correct
10 Correct 9129 ms 72472 KB Output is correct
11 Correct 9087 ms 73372 KB Output is correct
12 Correct 8889 ms 73472 KB Output is correct
13 Correct 8929 ms 72804 KB Output is correct
14 Correct 9257 ms 72284 KB Output is correct
15 Correct 9227 ms 75436 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 8845 ms 73204 KB Output is correct
18 Correct 6842 ms 75820 KB Output is correct
19 Correct 9229 ms 75296 KB Output is correct
20 Correct 9197 ms 75376 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 8958 ms 75296 KB Output is correct
24 Correct 8840 ms 73108 KB Output is correct
25 Correct 6878 ms 75624 KB Output is correct
26 Correct 3576 ms 34708 KB Output is correct
27 Correct 3582 ms 34672 KB Output is correct
28 Correct 58 ms 5280 KB Output is correct
29 Correct 3402 ms 33964 KB Output is correct
30 Correct 3292 ms 33940 KB Output is correct
31 Correct 2514 ms 34552 KB Output is correct
32 Correct 2682 ms 32916 KB Output is correct
33 Correct 9892 ms 77420 KB Output is correct
34 Execution timed out 10089 ms 75404 KB Time limit exceeded
35 Halted 0 ms 0 KB -