oj.uz

Submission #701862

# Submission time Handle Problem Language Result Execution time Memory
701862 2023-02-22T08:15:17 Z baokhue232005 Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 84772 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;
}

int retro(int cut){
    int cry = cut + 1;
    memset(ftree, 0, sizeof(ftree));
    int res = 0;
    vector<iii> qry;
    for1(i, 1, n){
        qry.pb({cy[i], ii(-2, cx[i])});
        qry.pb({cy[i] - cry, ii(-1, cx[i] + cut)});
        qry.pb({cy[i] - cry, ii(1 , cx[i] - cry)});
        qry.pb({cy[i] + cut, ii(1 , cx[i] + cut)});
        qry.pb({cy[i] + cut, ii(-1, cx[i] - cry)});
    }
    sort(all(qry));
    for(iii pr : qry){
        int cof = pr.se.fi;
        int plc = pr.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:119: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]
  119 |     while(ans.size() < k) ans.pb(r);
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9096 KB Output is correct
2 Correct 72 ms 9024 KB Output is correct
3 Correct 59 ms 8984 KB Output is correct
4 Correct 62 ms 9016 KB Output is correct
5 Correct 64 ms 7960 KB Output is correct
6 Correct 25 ms 4628 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6873 ms 84576 KB Output is correct
2 Correct 7047 ms 84400 KB Output is correct
3 Correct 54 ms 8876 KB Output is correct
4 Correct 6784 ms 84328 KB Output is correct
5 Correct 6915 ms 84380 KB Output is correct
6 Correct 6930 ms 84412 KB Output is correct
7 Correct 7046 ms 84400 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9766 ms 84316 KB Output is correct
2 Correct 9737 ms 84292 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 6828 ms 84772 KB Output is correct
5 Correct 7371 ms 84728 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9766 ms 84316 KB Output is correct
2 Correct 9737 ms 84292 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 6828 ms 84772 KB Output is correct
5 Correct 7371 ms 84728 KB Output is correct
6 Correct 9925 ms 84644 KB Output is correct
7 Correct 9842 ms 84596 KB Output is correct
8 Correct 5 ms 4180 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 9778 ms 84636 KB Output is correct
11 Correct 6856 ms 84648 KB Output is correct
12 Correct 7271 ms 84520 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9096 KB Output is correct
2 Correct 72 ms 9024 KB Output is correct
3 Correct 59 ms 8984 KB Output is correct
4 Correct 62 ms 9016 KB Output is correct
5 Correct 64 ms 7960 KB Output is correct
6 Correct 25 ms 4628 KB Output is correct
7 Correct 3896 ms 30968 KB Output is correct
8 Correct 4503 ms 31172 KB Output is correct
9 Correct 58 ms 9048 KB Output is correct
10 Correct 3880 ms 31128 KB Output is correct
11 Correct 3695 ms 30968 KB Output is correct
12 Correct 2895 ms 31076 KB Output is correct
13 Correct 2910 ms 31056 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9096 KB Output is correct
2 Correct 72 ms 9024 KB Output is correct
3 Correct 59 ms 8984 KB Output is correct
4 Correct 62 ms 9016 KB Output is correct
5 Correct 64 ms 7960 KB Output is correct
6 Correct 25 ms 4628 KB Output is correct
7 Correct 6873 ms 84576 KB Output is correct
8 Correct 7047 ms 84400 KB Output is correct
9 Correct 54 ms 8876 KB Output is correct
10 Correct 6784 ms 84328 KB Output is correct
11 Correct 6915 ms 84380 KB Output is correct
12 Correct 6930 ms 84412 KB Output is correct
13 Correct 7046 ms 84400 KB Output is correct
14 Correct 9766 ms 84316 KB Output is correct
15 Correct 9737 ms 84292 KB Output is correct
16 Correct 5 ms 4180 KB Output is correct
17 Correct 6828 ms 84772 KB Output is correct
18 Correct 7371 ms 84728 KB Output is correct
19 Correct 9925 ms 84644 KB Output is correct
20 Correct 9842 ms 84596 KB Output is correct
21 Correct 5 ms 4180 KB Output is correct
22 Correct 5 ms 4180 KB Output is correct
23 Correct 9778 ms 84636 KB Output is correct
24 Correct 6856 ms 84648 KB Output is correct
25 Correct 7271 ms 84520 KB Output is correct
26 Correct 3896 ms 30968 KB Output is correct
27 Correct 4503 ms 31172 KB Output is correct
28 Correct 58 ms 9048 KB Output is correct
29 Correct 3880 ms 31128 KB Output is correct
30 Correct 3695 ms 30968 KB Output is correct
31 Correct 2895 ms 31076 KB Output is correct
32 Correct 2910 ms 31056 KB Output is correct
33 Execution timed out 10070 ms 84244 KB Time limit exceeded
34 Halted 0 ms 0 KB -