oj.uz

Submission #701851

# Submission time Handle Problem Language Result Execution time Memory
701851 2023-02-22T07:53:59 Z baokhue232005 Road Construction (JOI21_road_construction) C++14
6 / 100
 9674 ms 89488 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 * 2;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 9064 KB Output is correct
2 Correct 345 ms 9068 KB Output is correct
3 Incorrect 321 ms 9032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6859 ms 87116 KB Output is correct
2 Correct 6913 ms 87244 KB Output is correct
3 Correct 323 ms 9024 KB Output is correct
4 Correct 6808 ms 87092 KB Output is correct
5 Correct 7030 ms 87108 KB Output is correct
6 Correct 7043 ms 87176 KB Output is correct
7 Correct 6839 ms 87272 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9595 ms 89436 KB Output is correct
2 Correct 9674 ms 89488 KB Output is correct
3 Incorrect 5 ms 4180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9595 ms 89436 KB Output is correct
2 Correct 9674 ms 89488 KB Output is correct
3 Incorrect 5 ms 4180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 9064 KB Output is correct
2 Correct 345 ms 9068 KB Output is correct
3 Incorrect 321 ms 9032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 9064 KB Output is correct
2 Correct 345 ms 9068 KB Output is correct
3 Incorrect 321 ms 9032 KB Output isn't correct
4 Halted 0 ms 0 KB -