oj.uz

Submission #701867

# Submission time Handle Problem Language Result Execution time Memory
701867 2023-02-22T08:21:42 Z baokhue232005 Road Construction (JOI21_road_construction) C++17
32 / 100
 3563 ms 60184 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];
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 72 ms 9000 KB Output is correct
2 Correct 69 ms 9028 KB Output is correct
3 Correct 54 ms 9100 KB Output is correct
4 Correct 68 ms 9160 KB Output is correct
5 Correct 74 ms 7968 KB Output is correct
6 Correct 22 ms 4408 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 60172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 60184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 60184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9000 KB Output is correct
2 Correct 69 ms 9028 KB Output is correct
3 Correct 54 ms 9100 KB Output is correct
4 Correct 68 ms 9160 KB Output is correct
5 Correct 74 ms 7968 KB Output is correct
6 Correct 22 ms 4408 KB Output is correct
7 Correct 3563 ms 24016 KB Output is correct
8 Correct 3533 ms 23976 KB Output is correct
9 Correct 59 ms 9176 KB Output is correct
10 Correct 3383 ms 23524 KB Output is correct
11 Correct 3166 ms 27756 KB Output is correct
12 Correct 2238 ms 23988 KB Output is correct
13 Correct 2376 ms 22952 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 9000 KB Output is correct
2 Correct 69 ms 9028 KB Output is correct
3 Correct 54 ms 9100 KB Output is correct
4 Correct 68 ms 9160 KB Output is correct
5 Correct 74 ms 7968 KB Output is correct
6 Correct 22 ms 4408 KB Output is correct
7 Runtime error 99 ms 60172 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -