oj.uz

Submission #701855

# Submission time Handle Problem Language Result Execution time Memory
701855 2023-02-22T08:04:19 Z baokhue232005 Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 84260 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 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:118: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]
  118 |     while(ans.size() < k) ans.pb(r);
      |           ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 9132 KB Output is correct
2 Correct 338 ms 9088 KB Output is correct
3 Correct 326 ms 8944 KB Output is correct
4 Correct 320 ms 9100 KB Output is correct
5 Correct 326 ms 7932 KB Output is correct
6 Correct 28 ms 4624 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7257 ms 84244 KB Output is correct
2 Correct 7493 ms 84152 KB Output is correct
3 Correct 328 ms 9016 KB Output is correct
4 Correct 7247 ms 84212 KB Output is correct
5 Correct 7364 ms 84260 KB Output is correct
6 Correct 7413 ms 84024 KB Output is correct
7 Correct 7523 ms 84092 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 84180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 84180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 9132 KB Output is correct
2 Correct 338 ms 9088 KB Output is correct
3 Correct 326 ms 8944 KB Output is correct
4 Correct 320 ms 9100 KB Output is correct
5 Correct 326 ms 7932 KB Output is correct
6 Correct 28 ms 4624 KB Output is correct
7 Correct 4226 ms 32836 KB Output is correct
8 Correct 4240 ms 32828 KB Output is correct
9 Correct 329 ms 9032 KB Output is correct
10 Correct 4051 ms 32852 KB Output is correct
11 Correct 3871 ms 32832 KB Output is correct
12 Correct 3001 ms 32832 KB Output is correct
13 Correct 3129 ms 32840 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 9132 KB Output is correct
2 Correct 338 ms 9088 KB Output is correct
3 Correct 326 ms 8944 KB Output is correct
4 Correct 320 ms 9100 KB Output is correct
5 Correct 326 ms 7932 KB Output is correct
6 Correct 28 ms 4624 KB Output is correct
7 Correct 7257 ms 84244 KB Output is correct
8 Correct 7493 ms 84152 KB Output is correct
9 Correct 328 ms 9016 KB Output is correct
10 Correct 7247 ms 84212 KB Output is correct
11 Correct 7364 ms 84260 KB Output is correct
12 Correct 7413 ms 84024 KB Output is correct
13 Correct 7523 ms 84092 KB Output is correct
14 Execution timed out 10042 ms 84180 KB Time limit exceeded
15 Halted 0 ms 0 KB -