제출 #991073

#제출 시각아이디문제언어결과실행 시간메모리
991073User0069팀들 (IOI15_teams)C++17
100 / 100
3785 ms163768 KiB
#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"; // } //}

컴파일 시 표준 에러 (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;
      |                  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...