oj.uz

Submission #474506

# Submission time Handle Problem Language Result Execution time Memory
474506 2021-09-18T14:54:14 Z balbit Road Construction (JOI21_road_construction) C++14
100 / 100
 2448 ms 511336 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 2e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 25e4+5;
const int mlog = maxn * __lg(maxn);

pii s[mlog*8];
int lc[mlog*8], rc[mlog*8];

int IT = 0;
int n;

//int x[maxn], y[maxn];

int build (int l=0, int r=n-1) {
    int o = IT++;
    if (l ==r ) {
        s[o] = {-iinf,-1};
        return o;
    }
    int mid = (l+r)/2;
    lc[o] = build(l,mid);
    rc[o] = build(mid+1,r);
    s[o] = {-iinf,-1};
    return o;
}

int MO (int p, int v, int o, int l=0, int r=n-1) {
//    bug(o);
    if (l > p || r < p) return o;
    int newo = IT++;
    if (l == r) {
        s[newo] = {v,v==-iinf?-1:l};
        return newo;
    }
    int mid = (l+r)/2;
    lc[newo] = MO(p,v,lc[o],l,mid);
    rc[newo] = MO(p,v,rc[o],mid+1,r);
//    bug(newo, lc[newo], rc[newo], o, lc[o], rc[o]);
    s[newo] = max(s[lc[newo]], s[rc[newo]]);
    return newo;
}

pii QU(int L, int R, int o, int l=0, int r=n-1) {
    if (l > R || r < L) return {-iinf,-1};
    if (l >= L && r <= R) return s[o];
    int mid = (l+r)/2;
    return max(
               QU(L,R,lc[o], l,mid),
               QU(L,R,rc[o], mid+1,r)
               );
}

int dlp[maxn], dup[maxn];
int version[maxn];

struct gp{
    int d, i, where;
    bool up;
    bool operator < (const gp &b) const {
        return d > b.d;
    }
};

signed main(){
    IOS();
    int k; cin>>n>>k;
    vector<pii> pt;
    vector<pii> ypos;
    REP(i,n) {
        int a,b; cin>>a>>b;
        ypos.pb({a,b});
        pt.pb({a,b});
    }
    SORT_UNIQUE(ypos);
    sort(ALL(pt), [&](pii a, pii b) {return a.f != b.f?a.f<b.f: a.s<b.s;});
    auto cmp = [&](pii a, pii b) {return a.s != b.s?a.s<b.s: a.f<b.f;};
    sort(ALL(ypos), cmp);

    auto gety = [&](pii tt) {return lower_bound(ALL(ypos), tt, cmp) - ypos.begin();};
    dup[0] = build();
    dlp[0] = build();

    priority_queue<gp > pq;
    REP(i,n) {
        int x = pt[i].f, y = pt[i].s;
        int Y = gety(pt[i]);
        bug(x,y,Y);
//        bug(x-y-QU(Y+1, n-1, dup[i]));
        pii tmp = QU(Y+1, n-1, dup[i]);
        pq.push({x-y-tmp.f, i, tmp.s, 1});
        dup[i+1] = MO(Y, x-y, dup[i]);
        tmp = QU(0, Y, dlp[i]);
        pq.push({x+y-tmp.f, i, tmp.s, 0});
        bug(x+y-tmp.f, tmp.s);
        dlp[i+1] = MO(Y, x+y, dlp[i]);
    }



    while (k) {
        gp G = pq.top(); pq.pop();
        if (G.where == -1) continue;
//        if (version[G.i] != G.v) continue;
//        bug(G.i, G.d, G.up, G.where);
//        ++version[G.i]; // it is correct, and it's updated
        int x = pt[G.i].f, y = pt[G.i].s;
        int Y = gety(pt[G.i]);
//        bug(x,y,Y);

        cout<<G.d<<endl;
        int newd, where;
        if (G.up) {
            dup[G.i] = MO(G.where, -iinf, dup[G.i]);
            pii tmp = QU(Y+1, n-1, dup[G.i]);
            newd = x-y-tmp.f;
            where = tmp.s;
        }else{
            dlp[G.i] = MO(G.where, -iinf, dlp[G.i]);
            pii tmp = QU(0, Y, dlp[G.i]);
            newd = x+y-tmp.f;
            where = tmp.s;
        }
        if (where != -1)
            pq.push({ newd, G.i, where, G.up });
        --k;
    }




}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 89752 KB Output is correct
2 Correct 402 ms 89804 KB Output is correct
3 Correct 348 ms 86232 KB Output is correct
4 Correct 292 ms 86216 KB Output is correct
5 Correct 371 ms 88640 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 505388 KB Output is correct
2 Correct 1347 ms 505460 KB Output is correct
3 Correct 248 ms 86084 KB Output is correct
4 Correct 890 ms 505416 KB Output is correct
5 Correct 886 ms 505436 KB Output is correct
6 Correct 873 ms 505464 KB Output is correct
7 Correct 893 ms 504692 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1130 ms 355820 KB Output is correct
2 Correct 1181 ms 355896 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 521 ms 358788 KB Output is correct
5 Correct 715 ms 361200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1130 ms 355820 KB Output is correct
2 Correct 1181 ms 355896 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 521 ms 358788 KB Output is correct
5 Correct 715 ms 361200 KB Output is correct
6 Correct 1156 ms 360992 KB Output is correct
7 Correct 1184 ms 360956 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1206 ms 360932 KB Output is correct
11 Correct 550 ms 358896 KB Output is correct
12 Correct 764 ms 361200 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 89752 KB Output is correct
2 Correct 402 ms 89804 KB Output is correct
3 Correct 348 ms 86232 KB Output is correct
4 Correct 292 ms 86216 KB Output is correct
5 Correct 371 ms 88640 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 1421 ms 277228 KB Output is correct
8 Correct 1455 ms 277324 KB Output is correct
9 Correct 297 ms 86480 KB Output is correct
10 Correct 878 ms 276612 KB Output is correct
11 Correct 1085 ms 276688 KB Output is correct
12 Correct 740 ms 277136 KB Output is correct
13 Correct 779 ms 275856 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 89752 KB Output is correct
2 Correct 402 ms 89804 KB Output is correct
3 Correct 348 ms 86232 KB Output is correct
4 Correct 292 ms 86216 KB Output is correct
5 Correct 371 ms 88640 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 1315 ms 505388 KB Output is correct
8 Correct 1347 ms 505460 KB Output is correct
9 Correct 248 ms 86084 KB Output is correct
10 Correct 890 ms 505416 KB Output is correct
11 Correct 886 ms 505436 KB Output is correct
12 Correct 873 ms 505464 KB Output is correct
13 Correct 893 ms 504692 KB Output is correct
14 Correct 1130 ms 355820 KB Output is correct
15 Correct 1181 ms 355896 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 521 ms 358788 KB Output is correct
18 Correct 715 ms 361200 KB Output is correct
19 Correct 1156 ms 360992 KB Output is correct
20 Correct 1184 ms 360956 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1206 ms 360932 KB Output is correct
24 Correct 550 ms 358896 KB Output is correct
25 Correct 764 ms 361200 KB Output is correct
26 Correct 1421 ms 277228 KB Output is correct
27 Correct 1455 ms 277324 KB Output is correct
28 Correct 297 ms 86480 KB Output is correct
29 Correct 878 ms 276612 KB Output is correct
30 Correct 1085 ms 276688 KB Output is correct
31 Correct 740 ms 277136 KB Output is correct
32 Correct 779 ms 275856 KB Output is correct
33 Correct 2448 ms 511244 KB Output is correct
34 Correct 2369 ms 511332 KB Output is correct
35 Correct 1706 ms 510648 KB Output is correct
36 Correct 1228 ms 511320 KB Output is correct
37 Correct 1251 ms 511336 KB Output is correct
38 Correct 1465 ms 509988 KB Output is correct