oj.uz

Submission #701857

# Submission time Handle Problem Language Result Execution time Memory
701857 2023-02-22T08:11:21 Z baokhue232005 Road Construction (JOI21_road_construction) C++14
65 / 100
 10000 ms 89472 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 73 ms 9068 KB Output is correct
2 Correct 71 ms 9092 KB Output is correct
3 Correct 57 ms 8984 KB Output is correct
4 Correct 57 ms 9080 KB Output is correct
5 Correct 66 ms 7944 KB Output is correct
6 Correct 27 ms 4616 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6906 ms 84088 KB Output is correct
2 Correct 7033 ms 84080 KB Output is correct
3 Correct 53 ms 8828 KB Output is correct
4 Correct 6849 ms 84120 KB Output is correct
5 Correct 6947 ms 84000 KB Output is correct
6 Correct 6933 ms 84344 KB Output is correct
7 Correct 7024 ms 84200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9731 ms 84180 KB Output is correct
2 Correct 9781 ms 84292 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 6915 ms 86904 KB Output is correct
5 Correct 7314 ms 89388 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9731 ms 84180 KB Output is correct
2 Correct 9781 ms 84292 KB Output is correct
3 Correct 5 ms 4180 KB Output is correct
4 Correct 6915 ms 86904 KB Output is correct
5 Correct 7314 ms 89388 KB Output is correct
6 Correct 9854 ms 89136 KB Output is correct
7 Correct 9838 ms 89448 KB Output is correct
8 Correct 5 ms 4180 KB Output is correct
9 Correct 5 ms 4176 KB Output is correct
10 Correct 9735 ms 89312 KB Output is correct
11 Correct 6811 ms 86964 KB Output is correct
12 Correct 7287 ms 89472 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9068 KB Output is correct
2 Correct 71 ms 9092 KB Output is correct
3 Correct 57 ms 8984 KB Output is correct
4 Correct 57 ms 9080 KB Output is correct
5 Correct 66 ms 7944 KB Output is correct
6 Correct 27 ms 4616 KB Output is correct
7 Correct 3868 ms 30716 KB Output is correct
8 Correct 3901 ms 30768 KB Output is correct
9 Correct 58 ms 9092 KB Output is correct
10 Correct 3809 ms 30808 KB Output is correct
11 Correct 3595 ms 31044 KB Output is correct
12 Correct 2736 ms 30968 KB Output is correct
13 Correct 2886 ms 30984 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9068 KB Output is correct
2 Correct 71 ms 9092 KB Output is correct
3 Correct 57 ms 8984 KB Output is correct
4 Correct 57 ms 9080 KB Output is correct
5 Correct 66 ms 7944 KB Output is correct
6 Correct 27 ms 4616 KB Output is correct
7 Correct 6906 ms 84088 KB Output is correct
8 Correct 7033 ms 84080 KB Output is correct
9 Correct 53 ms 8828 KB Output is correct
10 Correct 6849 ms 84120 KB Output is correct
11 Correct 6947 ms 84000 KB Output is correct
12 Correct 6933 ms 84344 KB Output is correct
13 Correct 7024 ms 84200 KB Output is correct
14 Correct 9731 ms 84180 KB Output is correct
15 Correct 9781 ms 84292 KB Output is correct
16 Correct 5 ms 4180 KB Output is correct
17 Correct 6915 ms 86904 KB Output is correct
18 Correct 7314 ms 89388 KB Output is correct
19 Correct 9854 ms 89136 KB Output is correct
20 Correct 9838 ms 89448 KB Output is correct
21 Correct 5 ms 4180 KB Output is correct
22 Correct 5 ms 4176 KB Output is correct
23 Correct 9735 ms 89312 KB Output is correct
24 Correct 6811 ms 86964 KB Output is correct
25 Correct 7287 ms 89472 KB Output is correct
26 Correct 3868 ms 30716 KB Output is correct
27 Correct 3901 ms 30768 KB Output is correct
28 Correct 58 ms 9092 KB Output is correct
29 Correct 3809 ms 30808 KB Output is correct
30 Correct 3595 ms 31044 KB Output is correct
31 Correct 2736 ms 30968 KB Output is correct
32 Correct 2886 ms 30984 KB Output is correct
33 Execution timed out 10057 ms 89160 KB Time limit exceeded
34 Halted 0 ms 0 KB -