oj.uz

Submission #875303

# Submission time Handle Problem Language Result Execution time Memory
875303 2023-11-19T03:53:09 Z HuyQuang_re_Zero Teams (IOI15_teams) C++14
100 / 100
 1435 ms 407392 KB 
#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';
    }
}
*/

Compilation message

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23132 KB Output is correct
2 Correct 4 ms 23132 KB Output is correct
3 Correct 4 ms 23132 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 4 ms 23128 KB Output is correct
8 Correct 4 ms 23132 KB Output is correct
9 Correct 4 ms 23132 KB Output is correct
10 Correct 4 ms 23132 KB Output is correct
11 Correct 4 ms 23132 KB Output is correct
12 Correct 5 ms 23128 KB Output is correct
13 Correct 4 ms 23132 KB Output is correct
14 Correct 4 ms 23132 KB Output is correct
15 Correct 4 ms 23288 KB Output is correct
16 Correct 4 ms 23132 KB Output is correct
17 Correct 4 ms 23204 KB Output is correct
18 Correct 4 ms 23168 KB Output is correct
19 Correct 5 ms 23132 KB Output is correct
20 Correct 4 ms 23132 KB Output is correct
21 Correct 4 ms 23132 KB Output is correct
22 Correct 4 ms 23224 KB Output is correct
23 Correct 4 ms 23132 KB Output is correct
24 Correct 5 ms 23140 KB Output is correct
25 Correct 4 ms 23132 KB Output is correct
26 Correct 5 ms 23132 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 91708 KB Output is correct
2 Correct 115 ms 89780 KB Output is correct
3 Correct 127 ms 89724 KB Output is correct
4 Correct 120 ms 92100 KB Output is correct
5 Correct 82 ms 90552 KB Output is correct
6 Correct 82 ms 90384 KB Output is correct
7 Correct 83 ms 88368 KB Output is correct
8 Correct 80 ms 88352 KB Output is correct
9 Correct 97 ms 90316 KB Output is correct
10 Correct 84 ms 90808 KB Output is correct
11 Correct 75 ms 90812 KB Output is correct
12 Correct 80 ms 91064 KB Output is correct
13 Correct 100 ms 91576 KB Output is correct
14 Correct 97 ms 89944 KB Output is correct
15 Correct 116 ms 90552 KB Output is correct
16 Correct 114 ms 91064 KB Output is correct
17 Correct 85 ms 91488 KB Output is correct
18 Correct 89 ms 91468 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 90040 KB Output is correct
2 Correct 130 ms 92088 KB Output is correct
3 Correct 284 ms 95152 KB Output is correct
4 Correct 115 ms 90040 KB Output is correct
5 Correct 168 ms 91132 KB Output is correct
6 Correct 143 ms 90796 KB Output is correct
7 Correct 86 ms 88860 KB Output is correct
8 Correct 131 ms 90948 KB Output is correct
9 Correct 98 ms 90444 KB Output is correct
10 Correct 132 ms 91364 KB Output is correct
11 Correct 145 ms 91644 KB Output is correct
12 Correct 187 ms 91808 KB Output is correct
13 Correct 319 ms 92460 KB Output is correct
14 Correct 310 ms 95108 KB Output is correct
15 Correct 143 ms 91672 KB Output is correct
16 Correct 139 ms 91516 KB Output is correct
17 Correct 123 ms 92428 KB Output is correct
18 Correct 123 ms 92264 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 393636 KB Output is correct
2 Correct 778 ms 395708 KB Output is correct
3 Correct 1329 ms 403756 KB Output is correct
4 Correct 754 ms 393960 KB Output is correct
5 Correct 605 ms 391256 KB Output is correct
6 Correct 582 ms 391444 KB Output is correct
7 Correct 436 ms 385324 KB Output is correct
8 Correct 541 ms 391280 KB Output is correct
9 Correct 516 ms 390648 KB Output is correct
10 Correct 578 ms 393964 KB Output is correct
11 Correct 694 ms 394608 KB Output is correct
12 Correct 868 ms 395632 KB Output is correct
13 Correct 1358 ms 398696 KB Output is correct
14 Correct 1435 ms 407392 KB Output is correct
15 Correct 740 ms 399644 KB Output is correct
16 Correct 729 ms 399432 KB Output is correct
17 Correct 563 ms 398028 KB Output is correct
18 Correct 563 ms 397968 KB Output is correct