Submission #991073

#	Time	Username	Problem	Language	Result	Execution time	Memory
991073		User0069	Teams (IOI15_teams)	C++17	100 / 100	3785 ms	163768 KiB

teams

#include<bits/stdc++.h>
#include"teams.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int N,val[maxn*30],r[maxn*30],l[maxn*30],cur;
struct node
{
    node *l,*r;
    int val;
    node():l(NULL),r(NULL),val(0){};
};
int new_node()
{
    return ++cur;
}
int root[maxn];
vector<int> v[maxn];
int cons(int cl,int cr)
{
    int kk=new_node();
    if(cl==cr)
    {
        return kk;
    }
    int mid=(cl+cr)/2;
    l[kk]=cons(cl,mid);
    r[kk]=cons(mid+1,cr);
    return kk;
}
int update(int kk,int cl,int cr,int pos,int v)
{
    int kkk=new_node();
    l[kkk]=l[kk];
    r[kkk]=r[kk];
    val[kkk]=val[kk];
    if(cl==cr)
    {
        val[kkk]+=v;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) l[kkk]=update(l[kk],cl,mid,pos,v);
    else r[kkk]=update(r[kk],mid+1,cr,pos,v);
    val[kkk]=val[l[kkk]]+val[r[kkk]];
    return kkk;
}
int get(int kk,int cl,int cr,int L,int R )
{
    if(cl>R||cr<L) return 0;
    if(cl>=L&&cr<=R) return val[kk];
    int mid=(cl+cr)/2;
    return get(l[kk],cl,mid,L,R)+get(r[kk],mid+1,cr,L,R);
}
int cnt(int a,int b,int c,int d)
{
    return get(root[b],0,N,c,d)-((a>0)?get(root[a-1],0,N,c,d):0);
}
void init(int32_t n,int32_t* a,int32_t* b)
{
    N=n;
    root[0]=cons(0,n);
    for(int i=0;i<n;i++)
    {
        v[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        root[i]=root[i-1];
        for(int x:v[i])
        {
            root[i]=update(root[i],0,n,x,1);
        }
    }
    root[n+1]=root[n];
}
struct ele
{
    int a,b,range,rmd;
};
int32_t can(int32_t m,int32_t* k)
{
    sort(k,k+m);
//    vector<pii> v;
//    int cur=k[0],num=1;
//    for(int i=1;i<m;i++)
//    {
//        if(k[i]==cur)
//        {
//            num++;
//        }
//        else
//        {
//            v.push_back({cur,num});
//            num=1;
//            cur=k[i];
//        }
//    }
//    v.push_back({cur,num});
    vector<ele> st;
    st.push_back({0,0,N,0});
    for(int i=0;i<m;i++)
    {
        int prev,late,a,b,sum=0;
        a=k[i];
        prev=st.back().a;
        b=prev+1;
        late=(i==m-1)?N+1:k[i+1];
        int ra=k[i]-1;
        int lmao=-1;
        while(st.back().range<=ra)
        {
            lmao=st.back().b;
            st.pop_back();
        }
        if(lmao!=-1) st.push_back({prev,lmao,ra,0});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
        while(!st.empty()&&sum+(lmao=cnt(ra+1,st.back().range,b,k[i]))<k[i])
        {
            b=st.back().b;
            sum+=lmao+st.back().rmd;
            ra=st.back().range;
            st.pop_back();
        }
        if(st.empty()) return 0;
        int l=ra,r=st.back().range,ans=-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum+cnt(ra+1,mid,b,k[i])>=k[i])
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        st.push_back({a,b,ans,sum+cnt(ra+1,ans,b,k[i])-k[i]});
//        for(ele w:st)
//        {
//            cout<<w.a<<" "<<w.b<<" "<<w.range<<" "<<w.rmd<<" ; ";
//        }
//        cout<<"\n";
    }
    return 1;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    int n,q;
//    cin>>n>>q;
//    int32_t _a[n],_b[n];
//    for(int i=0;i<n;i++)
//    {
//        cin>>_a[i]>>_b[i];
//    }
//    init(n,_a,_b);
//    while(q--)
//    {
//        int32_t _m;
//        cin>>_m;
//        int32_t _k[_m];
//        for(int i=0;i<_m;i++)
//        {
//            cin>>_k[i];
//        }
//        cout<<can(_m,_k)<<"\n";
//    }
//}

Compilation message (stderr)

teams.cpp: In function 'int update(int, int, int, int, int)':
teams.cpp:44:45: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   44 | int update(int kk,int cl,int cr,int pos,int v)
      |                                         ~~~~^
teams.cpp:31:13: note: shadowed declaration is here
   31 | vector<int> v[maxn];
      |             ^
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:143:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |             ^
teams.cpp:19:31: note: shadowed declaration is here
   19 | int N,val[maxn*30],r[maxn*30],l[maxn*30],cur;
      |                               ^
teams.cpp:143:18: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  143 |         int l=ra,r=st.back().range,ans=-1;
      |                  ^
teams.cpp:19:20: note: shadowed declaration is here
   19 | int N,val[maxn*30],r[maxn*30],l[maxn*30],cur;
      |                    ^
teams.cpp:117:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
  117 |         int prev,late,a,b,sum=0;
      |                  ^~~~

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