제출 #745671

#제출 시각아이디문제언어결과실행 시간메모리
745671ogibogi2004팀들 (IOI15_teams)C++14
77 / 100
1075 ms370484 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; const int MAXN=1e6+6; int n; int a[MAXN]; int b[MAXN]; struct node { int val; node *l, *r; node(int x){ val=x; l=nullptr; r=nullptr; } node(node *_l,node *_r) { l=_l; r=_r; val=0; if(l)val+=l->val; if(r)val+=r->val; } node(node *t) { val=t->val; l=t->l; r=t->r; } }; node *update(node *t,int val,int pos,int l=1,int r=n) { //cerr<<"update "<<l<<" "<<r<<endl; if(l==r)return new node(val); int mid=(l+r)/2; if(pos>mid) { if(t==nullptr)return new node(nullptr, update(nullptr,val,pos, mid+1,r)); else return new node(t->l, update(t->r,val,pos, mid+1,r)); } else { if(t==nullptr)return new node(update(nullptr,val,pos,l,mid), nullptr); else return new node(update(t->l,val,pos,l,mid), t->r); } } int query(node *t,int ql,int qr,int l=1,int r=n) { //cerr<<"query "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl; if(ql>r)return 0; if(t==nullptr)return 0; if(qr<l)return 0; if(l>=ql&&r<=qr)return t->val; int mid=(l+r)/2; return query(t->l,ql,qr,l,mid)+query(t->r,ql,qr,mid+1,r); } node *roots[MAXN]; struct segment { int l,r; }; vector<segment>v; bool cmp(segment s1,segment s2) { if(s1.r!=s2.r)return s1.r<s2.r; else return s1.l<s2.l; } vector<segment>s1[MAXN]; int sum[MAXN]; void init(int N, int A[], int B[]) { n=N; for(int i=0;i<N;i++) { a[i]=A[i]; b[i]=B[i]; v.push_back({A[i],B[i]}); } sort(v.rbegin(),v.rend(),cmp); for(auto xd:v) { s1[xd.r].push_back(xd); } roots[n+1]=nullptr; for(int i=n;i>=1;i--) { roots[i]=roots[i+1]; //cout<<"???\n"; { for(auto xd:s1[i]) { ++sum[xd.l]; roots[i]=update(roots[i],sum[xd.l],xd.l,1,n); //cerr<<" "<<xd.l<<" ^^"<<endl; } } } } int m; int k[MAXN]; int dp[MAXN]; int get_value1(int x) { node* root_we_need = roots[x]; return query(root_we_need,1,x,1,n); } int get_value(int i1,int i2) { if(k[i1]+1>k[i2])return 0; //should return no. of segments with k[i2]>=l>k[i1] and r>=k[i2] //persistent segment tree can do :( node *root_we_need = roots[k[i2]]; return query(root_we_need, k[i1]+1,k[i2],1,n); } int can(int M, int K[]) { //cerr<<"========query========="; sort(K,K+M); int sumk=0; for(int i=0;i<M;i++) { k[i]=K[i]; sumk+=k[i]; } if(sumk>n)return 0; m=M; dp[0]=get_value1(K[0])-K[0]; if(dp[0]<0)return 0; vector<int>ids; ids.push_back(0); //cerr<<"0 : "<<dp[0]<<endl; for(int i=1;i<m;i++) { while(ids.size()>1) { int id1=ids[ids.size()-2]; int id2=ids[ids.size()-1]; if(get_value(id1, i)+dp[id1]<=get_value(id2, i)+dp[id2]) { ids.pop_back(); } else { break; } } dp[i]=min(dp[ids.back()]+get_value(ids.back(), i)-K[i],get_value1(K[i])-K[i]); //cerr<<i<<" : "<<dp[i]<<endl; if(dp[i]<0)return 0; ids.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...