Submission #474505

#	Time	Username	Problem	Language	Result	Execution time	Memory
474505		balbit	Road Construction (JOI21_road_construction)	C++14	6 / 100	1148 ms	253576 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#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: 0 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35