Submission #70700

#TimeUsernameProblemLanguageResultExecution timeMemory
70700Sa1378Teams (IOI15_teams)C++17
0 / 100
4027 ms10860 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define N ((int)101*1000) #define K ((int)22) #define SQ ((int)500) int n,pos[N]; pair <int,int> a[N]; int seg[K][N]; void build(int xl=0,int xr=n,int h=0) { if(xl==xr-1) { seg[h][xl]=a[xl].second; return ; } int mid=(xl+xr)/2; build(xl,mid,h+1); build(mid,xr,h+1); merge(seg[h+1]+xl,seg[h+1]+mid,seg[h+1]+mid,seg[h+1]+xr,seg[h]+xl); } int query(int q,int val,int xl=0,int xr=n,int h=0) { int res=0; for(int i=0;i<n;i++) if(a[i].first<=q && a[i].second>=val) res++; return res;/* if(xr<=q)return xr-(lower_bound(seg[h]+xl,seg[h]+xr,val)-(seg[h]+xl)); int mid=(xl+xr)/2; int res=query(q,val,xl,mid,h+1); if(mid<q)res+=query(q,val,mid,xr,h+1); return res;*/ } void init(int n2, int A[], int B[]) { n=n2; for(int i=0;i<n;i++)a[i]={A[i],B[i]}; sort(a,a+n); for(int i=1,j=0;i<=n;i++) { while(j<n && a[j].first<=i)j++; pos[i]=j; } //build(); } pair <int,int> b[N]; int cnt[SQ][SQ]; int can(int m, int k[]) { int m2=0,sum=0; sort(k,k+m); for(int i=0;i<m;i++)sum+=k[i]; if(sum>n)return 0; for(int i=0;i<m;i++) { b[m2]={k[i],0}; while(i<m && k[i]==b[m2].first)b[m2].second+=k[i],i++; m2++; } m=m2; for(int i=0;i<m;i++) for(int j=i;j<m;j++) cnt[i][j]=query(b[i].first,b[j].first); for(int i=m-1;i>=0;i--) for(int j=i;j<m;j++) cnt[i][j]+=-cnt[i][j+1]-((i>0)?cnt[i-1][j]:0)+((i>0)?cnt[i-1][j+1]:0); for(int i=0;i<m;i++) { // cout<<i<<"||| \n"; // for(int j=0;j<m;j++)cout<<cnt[i][j]<<"\n"; int j=i; for(;j<m;j++) { // cout<<b[i].second<<" "<<cnt[i][j] if(b[i].second<=cnt[i][j]) { // cout<<"hir"; cnt[i][j]-=b[i].second; b[i].second=0; break; } b[i].second-=cnt[i][j]; } // cout<<b[i].second<<"..\n"; if(b[i].second)return 0; for(;j<m;j++)cnt[i+1][j]+=cnt[i][j]; } return 1; }

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:25:32: warning: unused parameter 'xl' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=0)
                                ^
teams.cpp:25:41: warning: unused parameter 'xr' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=0)
                                         ^
teams.cpp:25:49: warning: unused parameter 'h' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=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...