oj.uz

Submission #701868

# Submission time Handle Problem Language Result Execution time Memory
701868 2023-02-22T08:22:26 Z baokhue232005 Road Construction (JOI21_road_construction) C++17
100 / 100
 9833 ms 62268 KB 
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define eb emplace_back
#define ii pair<int, int>
#define endl "\n";
#define iii pair<int, ii>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 500005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

int cx[maxN], cy[maxN];
vi ord;

int ftree[maxN];
void inc(int plc){
    while(plc < maxN){
        ++ftree[plc];
        plc += plc & -plc;
    }
}
int take(int plc){
    int res = 0;
    while(plc){
        res += ftree[plc];
        plc -= plc & -plc;
    }
    return res;
}

iii qry[maxN * 5];
int cnt = 0;

int retro(int cut){
    int cry = cut + 1;
    memset(ftree, 0, sizeof(ftree));
    int res = 0;
    cnt = 0;
    for1(i, 1, n){
        qry[cnt++] = {cy[i], ii(-2, cx[i])};
        qry[cnt++] = {cy[i] - cry, ii(-1, cx[i] + cut)};
        qry[cnt++] = {cy[i] - cry, ii(1 , cx[i] - cry)};
        qry[cnt++] = {cy[i] + cut, ii(1 , cx[i] + cut)};
        qry[cnt++] = {cy[i] + cut, ii(-1, cx[i] - cry)};
    }
    sort(qry, qry + cnt);
    for1(i, 0, cnt - 1){
        int cof = qry[i].se.fi;
        int plc = qry[i].se.se;
        plc = upper_bound(all(ord), plc) - ord.begin() - 1;
        if(cof == -2) inc(plc);
        else res += take(plc) * cof;
    }
    res -= n;
    assert(res % 2 == 0);
    return res / 2;
}

signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for1(i, 1, n){
        cin >> x >> y;
        cx[i] = x + y;
        cy[i] = x - y;
        ord.pb(cx[i]);
    }
    ord.pb(-oo);
    ord.pb(oo);
    sort(all(ord)); ord.resize(unique(all(ord)) - ord.begin());
    int l = 1, r = mod * 10;
    while(l != r){
        int mid = (l + r) / 2;
        if(retro(mid) >= k) r = mid;
        else l = mid + 1;
    }
    vector<ii> tray;
    for1(i, 1, n) tray.pb(ii(cy[i], cx[i]));
    sort(all(tray));
    for(ii &pr : tray) swap(pr.fi, pr.se);
    set<ii> st;
    st.insert(ii(oo, oo));
    --l;
    vi ans;
    for(ii pr : tray){
        ii coke = {pr.fi - l, -oo};
        while(1){
            int dt = abs(coke.fi - pr.fi);
            int ds = abs(coke.se - pr.se);
            if(dt > l) break;
            if(ds <= l)
                ans.pb(max(ds, abs(coke.fi - pr.fi)));
            else st.erase(coke);
            coke = *st.upper_bound(coke);
        }
        st.insert(pr);
    }
    sort(all(ans));
    while(ans.size() < k) ans.pb(r);
    for(int cc : ans) cout << cc << endl;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:122: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]
  122 |     while(ans.size() < k) ans.pb(r);
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9012 KB Output is correct
2 Correct 66 ms 9008 KB Output is correct
3 Correct 54 ms 9032 KB Output is correct
4 Correct 54 ms 9080 KB Output is correct
5 Correct 62 ms 7892 KB Output is correct
6 Correct 21 ms 4420 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5621 ms 62144 KB Output is correct
2 Correct 5764 ms 62144 KB Output is correct
3 Correct 51 ms 8900 KB Output is correct
4 Correct 5561 ms 62012 KB Output is correct
5 Correct 5661 ms 62240 KB Output is correct
6 Correct 6252 ms 62268 KB Output is correct
7 Correct 5994 ms 61504 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8887 ms 52808 KB Output is correct
2 Correct 8705 ms 50624 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 5643 ms 58948 KB Output is correct
5 Correct 5996 ms 43720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8887 ms 52808 KB Output is correct
2 Correct 8705 ms 50624 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 5643 ms 58948 KB Output is correct
5 Correct 5996 ms 43720 KB Output is correct
6 Correct 8823 ms 47164 KB Output is correct
7 Correct 9470 ms 47680 KB Output is correct
8 Correct 7 ms 4268 KB Output is correct
9 Correct 6 ms 4256 KB Output is correct
10 Correct 9274 ms 51780 KB Output is correct
11 Correct 5652 ms 58944 KB Output is correct
12 Correct 5991 ms 43728 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9012 KB Output is correct
2 Correct 66 ms 9008 KB Output is correct
3 Correct 54 ms 9032 KB Output is correct
4 Correct 54 ms 9080 KB Output is correct
5 Correct 62 ms 7892 KB Output is correct
6 Correct 21 ms 4420 KB Output is correct
7 Correct 3567 ms 24024 KB Output is correct
8 Correct 3634 ms 24020 KB Output is correct
9 Correct 100 ms 9132 KB Output is correct
10 Correct 3548 ms 23500 KB Output is correct
11 Correct 3329 ms 27856 KB Output is correct
12 Correct 2339 ms 23976 KB Output is correct
13 Correct 2552 ms 22964 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 9012 KB Output is correct
2 Correct 66 ms 9008 KB Output is correct
3 Correct 54 ms 9032 KB Output is correct
4 Correct 54 ms 9080 KB Output is correct
5 Correct 62 ms 7892 KB Output is correct
6 Correct 21 ms 4420 KB Output is correct
7 Correct 5621 ms 62144 KB Output is correct
8 Correct 5764 ms 62144 KB Output is correct
9 Correct 51 ms 8900 KB Output is correct
10 Correct 5561 ms 62012 KB Output is correct
11 Correct 5661 ms 62240 KB Output is correct
12 Correct 6252 ms 62268 KB Output is correct
13 Correct 5994 ms 61504 KB Output is correct
14 Correct 8887 ms 52808 KB Output is correct
15 Correct 8705 ms 50624 KB Output is correct
16 Correct 5 ms 4180 KB Output is correct
17 Correct 5643 ms 58948 KB Output is correct
18 Correct 5996 ms 43720 KB Output is correct
19 Correct 8823 ms 47164 KB Output is correct
20 Correct 9470 ms 47680 KB Output is correct
21 Correct 7 ms 4268 KB Output is correct
22 Correct 6 ms 4256 KB Output is correct
23 Correct 9274 ms 51780 KB Output is correct
24 Correct 5652 ms 58944 KB Output is correct
25 Correct 5991 ms 43728 KB Output is correct
26 Correct 3567 ms 24024 KB Output is correct
27 Correct 3634 ms 24020 KB Output is correct
28 Correct 100 ms 9132 KB Output is correct
29 Correct 3548 ms 23500 KB Output is correct
30 Correct 3329 ms 27856 KB Output is correct
31 Correct 2339 ms 23976 KB Output is correct
32 Correct 2552 ms 22964 KB Output is correct
33 Correct 9797 ms 49348 KB Output is correct
34 Correct 9833 ms 54432 KB Output is correct
35 Correct 9461 ms 54184 KB Output is correct
36 Correct 5850 ms 54476 KB Output is correct
37 Correct 5893 ms 54432 KB Output is correct
38 Correct 5928 ms 53144 KB Output is correct