oj.uz

답안 #599297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
599297 2022-07-19T12:28:35 Z Bench0310 마상시합 토너먼트 (IOI12_tournament) C++17
100 / 100
 121 ms 36612 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=100000;
int tree[4*N];

void update(int idx,int l,int r,int pos,int x)
{
    if(l==r) tree[idx]=x;
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx]=tree[2*idx]+tree[2*idx+1];
    }
}

int descend(int idx,int l,int r,int p)
{
    if(l==r) return l;
    int m=(l+r)/2;
    if(p<=tree[2*idx]) return descend(2*idx,l,m,p);
    else return descend(2*idx+1,m+1,r,p-tree[2*idx]);
}

int GetBestPosition(int n,int m,int R,int *K,int *S,int *E)
{
    for(int i=1;i<=n;i++) update(1,1,n,i,1);
    vector<int> head(n+1,0);
    for(int i=1;i<=n;i++) head[i]=i;
    vector<int> v[n+m+1];
    for(int i=1;i<=m;i++)
    {
        int l=S[i-1]+1;
        int r=E[i-1]+1;
        for(int j=l;j<=r;j++)
        {
            int p=descend(1,1,n,l);
            v[n+i].push_back(head[p]);
            if(j<r) update(1,1,n,p,0);
            else head[p]=n+i;
        }
    }
    vector<array<int,18>> p(n+m+1);
    for(int i=0;i<=n+m;i++) p[i].fill(0);
    vector<int> tin(n+m+1,0);
    vector<int> tout(n+m+1,0);
    function<void(int)> dfs=[&](int a)
    {
        for(int i=1;i<18;i++) p[a][i]=p[p[a][i-1]][i-1];
        if(a<=n) tin[a]=tout[a]=a;
        for(int to:v[a])
        {
            p[to][0]=a;
            dfs(to);
            if(tin[a]==0) tin[a]=tin[to];
            tout[a]=tout[to];
        }
    };
    dfs(n+m);
    vector<int> val(n,0);
    for(int i=1;i<=n-1;i++) val[i]=(K[i-1]>R);
    vector<int> s(n+1,0);
    for(int i=2;i<=n;i++) s[i]=s[i-1]+val[i-1];
    auto sum=[&](int l,int r)->int{return (s[r]-s[l-1]);};
    array<int,2> res={-1,0};
    for(int i=1;i<=n;i++)
    {
        if(i>=2) s[i-1]+=val[i-1];
        int a=i;
        int cnt=0;
        for(int j=17;j>=0;j--)
        {
            if(p[a][j]!=0&&sum(tin[p[a][j]],tout[p[a][j]])==0)
            {
                a=p[a][j];
                cnt+=(1<<j);
            }
        }
        res=max(res,{cnt,-i});
    }
    return -res[1]-1;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 6 ms 2088 KB Output is correct
3 Correct 3 ms 960 KB Output is correct
4 Correct 6 ms 1748 KB Output is correct
5 Correct 10 ms 1748 KB Output is correct
6 Correct 9 ms 1364 KB Output is correct
7 Correct 5 ms 1984 KB Output is correct
8 Correct 5 ms 1860 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 6 ms 1620 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 11528 KB Output is correct
2 Correct 119 ms 36612 KB Output is correct
3 Correct 81 ms 14948 KB Output is correct
4 Correct 100 ms 31436 KB Output is correct
5 Correct 101 ms 32460 KB Output is correct
6 Correct 101 ms 22992 KB Output is correct
7 Correct 106 ms 33192 KB Output is correct
8 Correct 121 ms 33260 KB Output is correct
9 Correct 68 ms 14112 KB Output is correct
10 Correct 57 ms 14864 KB Output is correct