Submission #420594

#	Time	Username	Problem	Language	Result	Execution time	Memory
420594		Aldas25	Jousting tournament (IOI12_tournament)	C++14	49 / 100	201 ms	28100 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100;
const int MAXK = 30;

int n, c,r;
int k[MAXN], s[MAXN], e[MAXN];

ll tree[4*MAXN], lazy[4*MAXN][2];

void shift (int id) {
    if (lazy[id][0] != -1) {
        ll val = lazy[id][0];
        tree[2*id] = val;
        tree[2*id+1] = val;
        lazy[2*id][0] = lazy[2*id+1][0] = val;
        lazy[2*id][1] = lazy[2*id+1][1] = 0;
        lazy[id][0] = -1;
    }
    ll val = lazy[id][1];
    tree[2*id] -= val;
    tree[2*id+1] -= val;
    lazy[2*id][1] += val;
    lazy[2*id+1][1] += val;
    lazy[id][1] = 0;
}

void upd (int t, int fr, int to, ll val, int id = 1, int le = 0, int ri = n-1) {
    if (to < le || fr > ri) return;
    if (fr <= le && ri <= to) {
        if (t == 0) {
            tree[id] = val;
            lazy[id][0] = val;
            lazy[id][1] = 0;
        } else {
            tree[id] -= val;
            lazy[id][0] = -1;
            lazy[id][1] += val;
        }
        return;
    }
    int mid = (le+ri)/2;
    shift(id);
    upd(t, fr, to, val, 2*id, le, mid);
    upd (t, fr, to, val, 2*id+1, mid+1, ri);
    tree[id] = min(tree[2*id], tree[2*id+1]);
}

ll get (int p, int id = 1, int le = 0, int ri = n-1) {
    if (le == ri) return tree[id];
    int mid = (le+ri)/2;
    shift(id);
    if(p <= mid)
        return get(p, 2*id, le, mid);
    else
        return get(p, 2*id+1, mid+1, ri);
}

int par[MAXN], mn[MAXN], mx[MAXN];
int repr[MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    par[b] = a;
    mn[a] = max(mn[a], mn[b]);
    mx[a] = max(mx[a], mx[b]);
}

int parentInTree[4*MAXN];
vi adj[MAXN];
int dep[MAXN];
int lift[MAXN][MAXK];
int mxDep = 0;

void dfs (int v) {
    mxDep = max(mxDep, dep[v]);

    FOR(i, 1, MAXK-1)
        lift[v][i] = lift[lift[v][i-1]][i-1];

    for (int u : adj[v]) {
        dep[u] = dep[v]+1;
        lift[u][0] = v;
        dfs(u);
    }
}

int lca (int u, int v) {
    if (u == v) return u;
    if (dep[u] > dep[v])swap(u,v);
    int d = dep[v]-dep[u];
    FOR(i, 0, MAXK-1)
        if (d&(1<<i))
            v = lift[v][i];

    if (u == v) return u;

    for (int i = MAXK-1; i >= 0; i--) {
        if (lift[v][i] != lift[u][i]) {
            v = lift[v][i];
            u = lift[u][i];
        }
    }

    return lift[v][0];
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n = N;
    c = C;
    r = R;
    FOR(i, 0, n-1) {
        k[i] = K[i];
    }
    FOR(i, 0, c-1) {
        s[i] = S[i];
        e[i] = E[i];
    }

    FOR(i, 0, n-1) upd(0, i, i, i);

    FOR(i, 0, n-1) {
        par[i] = mn[i] = mx[i] = repr[i] = i;
    }

    FOR(i, 0, c-1) {
        int le = 0, ri = n-1;
        while (le < ri) {
            int mid = (le+ri)/2;
            if (get(mid) >= s[i]) ri = mid;
            else le = mid+1;
        }
        int cr = le;
        int fr = le, to = le;
        vi nodes;
        while (cr <= n-1 && get(cr) <= e[i]) {
            cr = find(cr);
            to = mx[cr];
            nodes.pb(cr);
            parentInTree[repr[cr]] = n+i;
            cr = to+1;
        }

        int lst = nodes[0];
        //for (int k = 1; k < (int)nodes)
        for (int x : nodes) unite(lst,x);
        repr[find(fr)] = n+i;

        upd(0, fr, to, get(fr));
        if (to+1 <= n-1) upd(1, to+1, n-1, e[i]-s[i]);

        //cout <<"   after i=" << i << " round s=" << s[i] << " e=" << e[i] << endl;
        //FOR(k, 0, n-1) cout << "       curval k=" << k << " val = " << get(k) << endl;
    }

   // FOR(i, 0, n+c-1) cout << " i = " << i << " par in tree = " << parentInTree[i] << endl;
    FOR(i, 0, n+c-2) adj[parentInTree[i]].pb(i);

    dfs(n+c-1);


    vi wh;
    FOR(i, 0, n-2) if (k[i] > r) wh.pb(i);

   /* cout << " white: ";
    for (int xx : wh) cout << xx << " ";
    cout << endl;*/

    //if ((int)wh.size() == 0) {
    //    return mxDep;
   // }

    int ans = 0;
    int ansId = 0;
    int whId = -1;
    FOR(i, 0, n-1) {
       // cout << " i  = " << i << endl;
        if (whId+1 < (int)wh.size() && wh[whId+1] < i)
            whId++;
        /// whId - before, whId+1 - after
        //cout << "   whId = " << whId << endl;
        int cur = dep[i];
        if (whId >= 0) {
            int anc = lca(wh[whId], i);
            //cout << "  anc wh = " << wh[whId] << " i = " << i << "  anc = " << anc << endl;
            int dst = dep[i] - dep[anc] - 1;
            cur = min(cur, dst);
        }
        if (whId+1 < (int)wh.size()) {
          //      cout << " adaasdass" << endl;
        //cout << "  bef anc wh = " << wh[whId+1]+1 << " i = " << i << endl;
            int anc =  lca(wh[whId+1]+1, i) ;
            //cout << "  anc wh = " << wh[whId+1]+1 << " i = " << i << "  anc = " << anc << endl;
            int dst = dep[i] - dep[anc] - 1;
            cur = min(cur, dst);
        }

        //cout << "  i = " << i << " cur = " << cur << endl;

        if (cur > ans) {
            ans = cur;
            ansId = i;
        }
    }

    return ansId;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51