Submission #705734

#	Time	Username	Problem	Language	Result	Execution time	Memory
705734		bin9638	Teams (IOI15_teams)	C++17	0 / 100	269 ms	35380 KiB

teams

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 500010
#define pb push_back
#define ii pair<int,int>

int n,cnt_l[N],cnt_r[N],l[N],r[N];

struct IT
{
    int t[N*4]={},ST[N*4]={};

    void down(int id)
    {
        t[id*2]+=t[id];
        t[id*2+1]+=t[id];
        ST[id*2]+=t[id];
        ST[id*2+1]+=t[id];
        t[id]=0;
    }

    void gan(int id,int l,int r,int i,int val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        gan(id*2,l,mid,i,val);
        gan(id*2+1,mid+1,r,i,val);
        ST[id]=min(ST[id*2],ST[id*2+1]);
    }

    void them(int id,int l,int r,int u,int v,int val)
    {
        if(l>v||r<u)
            return;
        if(l>=u&&r<=v)
        {
            ST[id]+=val;
            t[id]+=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        them(id*2,l,mid,u,v,val);
        them(id*2+1,mid+1,r,u,v,val);
        ST[id]=min(ST[id*2],ST[id*2+1]);
    }

    int get(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return 1000000000;
        if(l>=u&&r<=v)
            return ST[id];
        down(id);
        int mid=(l+r)/2;
        return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}T;

void init(int sl,int a[],int b[])
{
    n=sl;
    for(int i=1;i<=n;i++)
    {
        l[i]=a[i-1];
        r[i]=b[i-1];
        cnt_l[r[i]]++;
        cnt_r[l[i]]++;

    }
    for(int i=1;i<=n;i++)
        cnt_l[i]+=cnt_l[i-1];
    for(int i=n;i>=1;i--)
        cnt_r[i]+=cnt_r[i+1];
    for(int i=1;i<=n;i++)
        T.gan(1,1,n,i,-cnt_l[i]);
}

int can(int m,int sz[])
{
    ll sum=0;
    sort(sz,sz+m);
    for(int i=0;i<m;i++)
        sum+=1ll*sz[i];
    if(sum>n)
        return 0;
    for(int i=0;i<m;i++)
        T.them(1,1,n,sz[i],n,sz[i]);
    for(int sum_r=0,i=0;i<m;i++)
    {
        sum_r+=sz[i];
        //cout<<sz[i]<<" "<<sum_r<<" "<<cnt_r[sz[i]+1]<<" "<<sum_r-n+cnt_r[sz[i]+1]<<endl;
        if(sum_r-n+cnt_r[sz[i]+1]>0)
        {
            for(int i=0;i<m;i++)
                T.them(1,1,n,sz[i],n,-sz[i]);
            return 0;
        }
        if(sum_r-n+cnt_r[sz[i]+1]>T.get(1,1,n,1,sz[i]))
        {
            for(int i=0;i<m;i++)
                T.them(1,1,n,sz[i],n,-sz[i]);
            return 0;
        }
    }
    for(int i=0;i<m;i++)
        T.them(1,1,n,sz[i],n,-sz[i]);
    return 1;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
  //  ios::sync_with_stdio(0);
   // cin.tie(NULL);
   // cout.tie(NULL);
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
    }
    init(n,a,b);
    int q;
    cin>>q;
    while(q--)
    {
        int m;
        cin>>m;
        int k[m];
        for(int j=0;j<m;j++)
            cin>>k[j];
        cout<<can(m,k)<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message (stderr)

teams.cpp: In member function 'void IT::gan(int, int, int, int, int)':
teams.cpp:27:31: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   27 |     void gan(int id,int l,int r,int i,int val)
      |                           ~~~~^
teams.cpp:12:30: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                              ^
teams.cpp:27:25: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   27 |     void gan(int id,int l,int r,int i,int val)
      |                     ~~~~^
teams.cpp:12:25: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                         ^
teams.cpp: In member function 'void IT::them(int, int, int, int, int, int)':
teams.cpp:43:32: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   43 |     void them(int id,int l,int r,int u,int v,int val)
      |                            ~~~~^
teams.cpp:12:30: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                              ^
teams.cpp:43:26: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   43 |     void them(int id,int l,int r,int u,int v,int val)
      |                      ~~~~^
teams.cpp:12:25: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                         ^
teams.cpp: In member function 'int IT::get(int, int, int, int, int)':
teams.cpp:60:30: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   60 |     int get(int id,int l,int r,int u,int v)
      |                          ~~~~^
teams.cpp:12:30: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                              ^
teams.cpp:60:24: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   60 |     int get(int id,int l,int r,int u,int v)
      |                    ~~~~^
teams.cpp:12:25: note: shadowed declaration is here
   12 | int n,cnt_l[N],cnt_r[N],l[N],r[N];
      |                         ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:21: warning: declaration of 'i' shadows a previous local [-Wshadow]
  107 |             for(int i=0;i<m;i++)
      |                     ^
teams.cpp:101:21: note: shadowed declaration is here
  101 |     for(int sum_r=0,i=0;i<m;i++)
      |                     ^
teams.cpp:113:21: warning: declaration of 'i' shadows a previous local [-Wshadow]
  113 |             for(int i=0;i<m;i++)
      |                     ^
teams.cpp:101:21: note: shadowed declaration is here
  101 |     for(int sum_r=0,i=0;i<m;i++)
      |                     ^

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