제출 #875303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875303		HuyQuang_re_Zero	팀들 (IOI15_teams)	C++14	100 / 100	1435 ms	407392 KiB

teams

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "teams.h"
using namespace std;
struct Persistent
{
    Persistent *l,*r;
    int sum=0;
    void comp() { sum=l->sum+r->sum; }
} *ver[500005];
Persistent *build(Persistent *u,int l,int r)
{
    u=new Persistent();
    if(l==r) return u;
    int mid=(l+r)>>1;
    u->l=build(u->l,l,mid); u->r=build(u->r,mid+1,r);
    return u;
}
Persistent *update(Persistent *u,int l,int r,int x)
{
    Persistent *v=new Persistent();
    v->l=u->l;
    v->r=u->r;
    v->sum=u->sum;
    if(l==r) v->sum++;
    else
    {
        int mid=(l+r)>>1;
        if(x<=mid) v->l=update(u->l,l,mid,x);
        else v->r=update(u->r,mid+1,r,x);
        v->comp();
    }
    return v;
}


int st[4*500005];
Persistent *lz[4*500005];
void change(int id,Persistent *x)
{
    lz[id]=x;
    st[id]=x->sum;
}
void down(int id)
{
    Persistent *x=lz[id];
    if(x==NULL) return ;
    change(id*2,x->l); change(id*2+1,x->r);
    lz[id]=NULL;
}
void updateIT(int id,int l,int r,int u,int v,Persistent *x)
{
    if(u>r || v<l) return ;
    if(u<=l && r<=v) { change(id,x); return ; }
    down(id);
    int mid=(l+r)>>1;
    updateIT(id*2,l,mid,u,v,x->l); updateIT(id*2+1,mid+1,r,u,v,x->r);
    st[id]=st[id*2]+st[id*2+1];
}
int getIT(int id,int l,int r,int u,int v,Persistent *x)
{
    if(u>r || v<l) return 0;
    if(u<=l && r<=v) return x->sum-st[id];
    down(id);
    int mid=(l+r)>>1;
    return getIT(id*2,l,mid,u,v,x->l)+getIT(id*2+1,mid+1,r,u,v,x->r);
}
int Find(int id,int l,int r,Persistent *x,int k)
{
    if(l==r) return l;
    down(id);
    int mid=(l+r)>>1,t=x->l->sum-st[id*2];
    if(t>=k) return Find(id*2,l,mid,x->l,k);
    return Find(id*2+1,mid+1,r,x->r,k-t);
}


int n,m,i,a[500005],b[500005],cnt,Endn[500005],q,inST[500005],Begin[500005];
vector <int> vec[500005];
void init(int _n,int _a[],int _b[])
{
    n=_n;
    vector <II> VecB;
    for(i=0;i<n;i++) VecB.push_back({ _b[i],i });
    sort(VecB.begin(),VecB.end());
    for(II x:VecB)
    {
        inST[x.snd]=++cnt;
        if(Begin[x.fst]==0) Begin[x.fst]=cnt;
    }
    for(i=n;i>=1;i--)
        if(Begin[i]==0) Begin[i]=Begin[i+1];
    cnt=0;
    for(i=0;i<n;i++) vec[_a[i]].push_back(inST[i]);
    ver[0]=build(ver[0],1,n);
    for(i=1;i<=n;i++)
    {
        for(int x:vec[i]) cnt++,ver[cnt]=update(ver[cnt-1],1,n,x);
        Endn[i]=cnt;
    }
}
int can(int m,int _a[])
{
    for(i=m;i>=1;i--) a[i]=_a[i-1];
    sort(a+1,a+m+1);
    updateIT(1,1,n,1,n,ver[0]);
    for(i=1;i<=m;i++)
    {
        Persistent *u=ver[Endn[a[i]]];
        if(Begin[a[i]]==0) return 0;
        int k=getIT(1,1,n,1,Begin[a[i]]-1,u);
        if(getIT(1,1,n,1,n,u)<a[i]+k)
            return 0;
        int pos=Find(1,1,n,u,a[i]+k);
        updateIT(1,1,n,Begin[a[i]],pos,u);
    }
    return 1;
}

/*
int main()
{
    freopen("teams.inp","r",stdin);
    freopen("teams.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=0;i<n;i++) cin>>a[i]>>b[i];
    init(n,a,b);
    cin>>q;
    while(q--)
    {
        cin>>m;
        for(i=0;i<m;i++) cin>>a[i];
        cout<<can(m,a)<<'\n';
    }
}
*/

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:13: warning: declaration of 'm' shadows a global declaration [-Wshadow]
  115 | int can(int m,int _a[])
      |         ~~~~^
teams.cpp:91:7: note: shadowed declaration is here
   91 | int n,m,i,a[500005],b[500005],cnt,Endn[500005],q,inST[500005],Begin[500005];
      |       ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23