oj.uz

Submission #1035080

# Submission time Handle Problem Language Result Execution time Memory
1035080 2024-07-26T03:55:54 Z 12345678 Jousting tournament (IOI12_tournament) C++17
100 / 100
 327 ms 34132 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=1e5+5, kx=18;
 
int n, c[2*nx], rt, nd[nx], cur, pa[2*nx][kx], lvl[2*nx], in[2*nx], out[2*nx], t, res;
vector<int> d[2*nx];
 
void dfs(int u, int p)
{
    in[u]=++t;
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) dfs(v, u);
    out[u]=t;
    //cout<<"tour "<<u<<' '<<in[u]<<' '<<out[u]<<'\n';
}
 
struct segtree
{
    int d[8*nx];
    void build(int l, int r, int i)
    {
        d[i]=0;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]+=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql ,qr)+query(md+1, r, 2*i+1, ql, qr);
    }
    int query2(int l, int r, int i, int key)
    {
        if (l==r) return l;
        int md=(l+r)/2;
        if (d[2*i]>=key) return query2(l, md, 2*i, key);
        else return query2(md+1, r, 2*i+1, key-d[2*i]);
    }
} s;
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    n=cur=N;
    for (int i=1; i<=N; i++) nd[i]=i, s.update(1, N, 1, i, 1);
    for (int i=0; i<C; i++)
    {
        cur++;
        for (int j=S[i]+1; j<=E[i]+1; j++)
        {
            int idx=s.query2(1, N, 1, S[i]+1);
            d[cur].push_back(nd[idx]);
            if (j==E[i]+1) nd[idx]=cur;
            else s.update(1, N, 1, idx, -1);
        }
    }
    s.build(1, 2*N, 1);
    for (int i=2; i<=N; i++) c[i]=K[i-2]>R;
    rt=cur;
    dfs(rt, rt);
    for (int i=1; i<=N; i++) s.update(1, 2*N, 1, in[i], c[i]); //cout<<"update "<<i<<' '<<in[i]<<' '<<c[i]<<'\n';
    pair<int, int> mx={-1, -1};
    if (R==N-1)
    {
        for (int i=1; i<=N; i++) mx=max(mx, {lvl[i]-1, -i});
        return cout<<-mx.second-1, 0;
    }
    for (int i=1; i<=N; i++)
    {
        if (i!=1) 
        {
            s.update(1, 2*N, 1, in[i-1], -c[i-1]);
            s.update(1, 2*N, 1, in[i], -c[i]);
            swap(c[i], c[i-1]);
            s.update(1, 2*N, 1, in[i-1], c[i-1]);
            s.update(1, 2*N, 1, in[i], c[i]);
        }
        int u=i;
        for (int j=kx-1; j>=0; j--) if (s.query(1, 2*N, 1, in[pa[u][j]], out[pa[u][j]])==0) u=pa[u][j];
        mx=max(mx, {lvl[i]-lvl[u], -i});
    }
    return -mx.second-1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 3 ms 5208 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 14 ms 6488 KB Output is correct
3 Correct 9 ms 5724 KB Output is correct
4 Correct 16 ms 6444 KB Output is correct
5 Correct 16 ms 6236 KB Output is correct
6 Correct 14 ms 5980 KB Output is correct
7 Correct 21 ms 6492 KB Output is correct
8 Correct 19 ms 6436 KB Output is correct
9 Correct 8 ms 5724 KB Output is correct
10 Correct 11 ms 6236 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 15304 KB Output is correct
2 Correct 320 ms 34132 KB Output is correct
3 Correct 173 ms 18384 KB Output is correct
4 Correct 288 ms 31312 KB Output is correct
5 Correct 327 ms 31572 KB Output is correct
6 Correct 210 ms 25424 KB Output is correct
7 Correct 322 ms 32192 KB Output is correct
8 Correct 311 ms 32408 KB Output is correct
9 Correct 190 ms 17608 KB Output is correct
10 Correct 156 ms 18204 KB Output is correct