oj.uz

답안 #223863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223863 2020-04-16T15:52:55 Z laoriu 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 239 ms 22008 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pp;
struct node
{
    int num,r,d,pos;
};
node it[400002];
int f[100002],ll[100002],rr[100002],pos[100002];
int rmq[100002][22];
void update(int id,int l,int r,int pos,node a)
{
    if (l>pos||r<pos) return;
    if (l==r)
    {
        it[id].num=a.num;it[id].r=a.r;
        it[id].d=a.d;it[id].pos=a.pos;return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,pos,a);
    update(id*2+1,mid+1,r,pos,a);
    it[id].num=it[id*2].num+it[id*2+1].num;
    it[id].r=max(it[id*2].r,it[id*2+1].r);
    it[id].d=max(it[id*2].d,it[id*2+1].d);
    if (it[id*2].d>=it[id*2+1].d) it[id].pos=it[id*2].pos;
    else it[id].pos=it[id*2+1].pos;
    if (it[id*2].d==it[id*2+1].d) it[id].pos=min(it[id*2].pos,it[id*2+1].pos);
}
node query(int id,int l,int r,int a,int b)
{
    if (l>b||r<a) return {0,0,-1,0};
    if (l>=a&&r<=b)
    {
        //cout<<"cac "<<l<<' '<<r<<' '<<it[id].pos<<endl;
        return it[id];
    }
    int mid=(l+r)/2;
    node x=query(id*2,l,mid,a,b);
    node y=query(id*2+1,mid+1,r,a,b);
    node ans;
    ans.num=x.num+y.num;
    ans.r=max(x.r,y.r);
    ans.d=max(x.d,y.d);
    if (x.d>y.d) ans.pos=x.pos;else ans.pos=y.pos;
    if (x.d==y.d) ans.pos=min(x.pos,y.pos);
    return ans;
}
int find_pos(int id,int l,int r,int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    if (it[id*2].num>=k) return find_pos(id*2,l,mid,k);
    else return find_pos(id*2+1,mid+1,r,k-it[id*2].num);
}
int GetBestPosition(int n,int k,int r,int A[],int L[],int R[])
{
    for (int i=n-1;i>=1;i--) A[i]=A[i-1];
    for (int i=1;i<=n;i++)
        update(1,1,n,i,{1,i,0,i});
    set <int> s;
    set <int>::iterator id;
    for (int i=1;i<=n;i++) s.insert(i);
    for (int i=0;i<k;i++)
    {
        L[i]++;R[i]++;
        int l=find_pos(1,1,n,L[i]);int r=find_pos(1,1,n,R[i]);
        node a=query(1,1,n,l,r);
        f[i]=a.d+1;ll[i]=l;rr[i]=a.r;
        pos[i]=a.pos;
      //  cout<<ll[i]<<' '<<rr[i]<<' '<<f[i]<<' '<<pos[i]<<endl;

        vector <int> P;
        id=s.lower_bound(l);

        for (id;id!=s.end();id++)
        {
            //cout<<*id<<' ';

            if ((*id)>r) break;
            P.push_back(*id);
            if ((*id)!=l) update(1,1,n,(*id),{0,0,-1,n});

        }
        //cout<<endl;
       /* id=s.lower_bound(l);
        for (id;id!=s.end();id++)
        {
            if ((*id)>r) break;
            if ((*id)!=l) s.erase(id);
        }*/
        for (int i=0;i<P.size();i++) if (P[i]!=l) s.erase(P[i]);
        update(1,1,n,l,{1,rr[i],f[i],pos[i]});

    }
    //return 0;
    for (int i=1;i<=n;i++) rmq[i][0]=A[i];
    for (int j=1;j<=20;j++)
        for (int i=1;i<=n;i++)
            if (i>=(1<<j))
        {
            rmq[i][j]=max(rmq[i][j-1],rmq[i-(1<<(j-1))][j-1]);
        }

    int res=0;int ans=1;
    for (int i=0;i<k;i++)
    {
        int vmax=0;
        for (int j=0;j<=20;j++)
            if ((1<<j)>rr[i]-ll[i]) break;
            else vmax=max(vmax,max(rmq[rr[i]-1][j],rmq[ll[i]+(1<<j)-1][j]));
        if(r>vmax)
        {
            if (res==f[i]) ans=min(ans,pos[i]);
            if (res<f[i])
            {
                res=f[i];
                ans=pos[i];
            }


        }
    }
    return ans-1;
}
/*int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("tournament.inp","r",stdin);
    freopen("tournament.out","w",stdout);
    int n,k,r,A[100002],L[100002],R[100002];
    cin>>n>>k>>r;
    for (int i=0;i<n-1;i++)
        cin>>A[i];
    for (int i=0;i<k;i++) cin>>L[i]>>R[i];
    cout<<GetBestPosition(n,k,r,A,L,R);
}*/

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:75:16: warning: statement has no effect [-Wunused-value]
         for (id;id!=s.end();id++)
                ^
tournament.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<P.size();i++) if (P[i]!=l) s.erase(P[i]);
                      ~^~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 13 ms 1536 KB Output is correct
3 Correct 9 ms 1408 KB Output is correct
4 Correct 14 ms 1408 KB Output is correct
5 Correct 12 ms 1408 KB Output is correct
6 Correct 13 ms 1408 KB Output is correct
7 Correct 13 ms 1536 KB Output is correct
8 Correct 13 ms 1408 KB Output is correct
9 Correct 8 ms 1408 KB Output is correct
10 Correct 15 ms 1408 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 10616 KB Output is correct
2 Correct 221 ms 22008 KB Output is correct
3 Correct 120 ms 18964 KB Output is correct
4 Correct 226 ms 22008 KB Output is correct
5 Correct 211 ms 21496 KB Output is correct
6 Correct 239 ms 20984 KB Output is correct
7 Correct 224 ms 22008 KB Output is correct
8 Correct 217 ms 22008 KB Output is correct
9 Correct 109 ms 18856 KB Output is correct
10 Correct 133 ms 18940 KB Output is correct