Submission #432814

#	Time	Username	Problem	Language	Result	Execution time	Memory
432814		MarcoMeijer	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	960 ms	56120 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }

const int N=(1<<20);

ii seg[N*2], seg2[N*2]; int laz[N*2];
void buildSeg(int p=1, int l=0, int r=N-1) {
    laz[p] = 0;
    if(l == r) {
        seg [p] = {0,l};
        seg2[p] = {0,l};
        return;
    }
    int m=(l+r)/2;
    buildSeg(p*2  ,l  ,m);
    buildSeg(p*2+1,m+1,r);
    seg [p] = min(seg [p*2], seg [p*2+1]);
    seg2[p] = max(seg2[p*2], seg2[p*2+1]);
}
void addSeg(int p, int v) {
    seg [p] = {seg [p].fi+v, seg [p].se};
    seg2[p] = {seg2[p].fi+v, seg2[p].se};
    laz [p] += v;
}
void push(int p) {
    addSeg(p*2  ,laz[p]);
    addSeg(p*2+1,laz[p]);
    laz[p] = 0;
}
void addSeg(int i, int j, int v, int p=1, int l=0, int r=N-1) {
    if(j < i) return;
    if(j < l || i > r) return;
    if(i <= l && j >= r) {
        addSeg(p,v);
        return;
    }
    push(p);
    int m=(l+r)/2;
    addSeg(i,j,v,p*2,l,m);
    addSeg(i,j,v,p*2+1,m+1,r);
    seg [p] = min(seg [p*2], seg [p*2+1]);
    seg2[p] = max(seg2[p*2], seg2[p*2+1]);
}

int p[N], r[N], sets;
void buildDSU(int dsuSize) {
    RE(i,dsuSize) p[i]=i, r[i]=0;
    sets = dsuSize;
}
int getSet(int i) {return i==p[i]?i:p[i]=getSet(p[i]);}
bool isSameSet(int i, int j) {return getSet(i)==getSet(j);}
void unionSet(int i, int j) {
    if(!isSameSet(i,j)) {
        i=p[i], j=p[j];
        sets--;
        if(r[i] > r[j]) {
            p[j] = i;
        } else {
            p[i] = j;
            if(r[i] == r[j]) r[j]++;
        }
    }
}


ll plan_roller_coaster(vi s, vi t) {
    s.pb(1e9); t.pb(1);
    int n = s.size();

    // coördinate compression
    vi difx;
    RE(i,n) difx.pb(s[i]), difx.pb(t[i]);
    sort(all(difx));
    difx.erase(unique(all(difx)), difx.end());
    RE(i,n) {
        s[i]=lower_bound(all(difx),s[i])-difx.begin();
        t[i]=lower_bound(all(difx),t[i])-difx.begin();
    }

    // create seg
    buildSeg();
    RE(i,n) {
        if(s[i] < t[i]) {
            addSeg(s[i],t[i]-1, 1);
        } else {
            addSeg(t[i],s[i]-1,-1);
        }
    }

    // create dsu
    buildDSU(difx.size());
    RE(i,n)
        unionSet(s[i],t[i]);

    // create forwards edges
    while(seg[1].fi < 0) {
        int i = seg[1].se;
        int x = seg[1].fi;
        addSeg(i,i,-x);
        unionSet(i,i+1);
    }

    ll ans = 0;
    // create backwards edges
    while(seg2[1].fi > 0) {
        int i = seg2[1].se;
        ll x = seg2[1].fi;
        addSeg(i,i,-x);
        unionSet(i,i+1);
        ans += x*ll(difx[i+1]-difx[i]);
    }

    // check if connected
    priority_queue<ii,vii,greater<ii>> pq;
    RE(i,difx.size()-1)
        if(!isSameSet(i,i+1))
            pq.push({difx[i+1]-difx[i], i});
    while(!pq.empty()) {
        ii p = pq.top(); pq.pop();
        int i = p.se;
        int x = p.fi;
        if(isSameSet(i,i+1)) continue;
        unionSet(i,i+1);
        ans += x;
    }

    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36