제출 #1088910

#제출 시각아이디문제언어결과실행 시간메모리
1088910yeediot팀들 (IOI15_teams)C++17
0 / 100
778 ms247700 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int mxn=5e5+5; const int inf=1e9; vector<int> segtree(mxn*20); vector<int> R(mxn*20),L(mxn*20); vector<int> root(mxn); int n; int cnt=0; int update(int node,int pos,int l=1,int r=n){ int x=++cnt; assert(x<mxn*20); L[x]=L[node]; R[x]=R[node]; segtree[x]=segtree[node]; if(l==r){ segtree[x]++; return x; } int mid=(l+r)/2; if(pos<=mid) L[x]=update(L[node],pos,l,mid); else R[x]=update(R[node],pos,mid+1,r); segtree[x]=segtree[L[x]]+segtree[R[x]]; return x; } int query(int node1,int node2,int tl,int tr,int l=1,int r=n){ if(r<tl or tr<l){ return 0; } if(tl<=l and r<=tr){ return segtree[node1]-segtree[node2]; } int mid=(l+r)/2; return query(L[node1],L[node2],tl,min(mid,tr),l,mid)+query(R[node1],R[node2],max(mid+1,tl),tr,mid+1,r); } int kth(int node1,int node2,int k,int l=1,int r=n){ if(l==r){ return l; } int sum=segtree[L[node1]]-segtree[L[node2]]; int mid=(l+r)/2; if(k<=sum) return kth(L[node1],L[node2],k,l,mid); else return kth(R[node1],R[node2],k-sum,mid+1,r); } void init(int N, int A[], int B[]) { n=N; vector<vector<int>> vec(n+1); for(int i=0;i<n;i++){ vec[A[i]].push_back(B[i]); } for(int i=1;i<=n;i++){ root[i]=root[i-1]; for(auto v:vec[i]){ root[i]=update(root[i],v); } } } int can(int M, int K[]) { sort(K,K+M); int m=M+1; vector<int> vec(m); for(int i=1;i<m;i++){ vec[i]=K[i-1]; } vector<int> rem(m); vector<int> H(m); vector<int> st; st.push_back(0); H[0]=n+1; for(int i=1;i<m;i++){ while(!st.empty() and H[st.back()]<=vec[i]){ st.pop_back(); } int sum=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],vec[i],n); //cout<<sum<<' '<<rem[st.back()]<<' '<<query(root[vec[i]],root[vec[st.back()]],vec[i],n)<<'\n'; if(sum<vec[i]){ return 0; } H[i]=vec[i]; int cur=vec[i]; while(!st.empty()){ int now=query(root[vec[i]],root[vec[st.back()]],H[i],H[st.back()]-1); //cout<<now<<'\n'; if(now>=cur){ int below=query(root[vec[i]],root[vec[st.back()]],1,H[i]-1); if(now==cur){ int all = query(root[vec[i]],root[vec[st.back()]],1,n); if(cur == all) H[i]=H[st.back()]; else H[i] = H[i]=kth(root[vec[i]],root[vec[st.back()]],below+cur+1); } else H[i]=kth(root[vec[i]],root[vec[st.back()]],below+cur+1); assert(H[i]<=H[st.back()]); rem[i]=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],H[i],n); break; } else{ H[i]=H[st.back()]; cur-=now; st.pop_back(); } } if(H[st.back()]==H[i]) st.pop_back(); st.push_back(i); } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...