제출 #282556

#제출 시각아이디문제언어결과실행 시간메모리
282556Nucleist마상시합 토너먼트 (IOI12_tournament)C++11
49 / 100
1051 ms22680 KiB
//Self-control leads to consistency. #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace __gnu_pbds; using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll int #define INF 1000000000 #define MOD 1000000007 #define pb push_back #define ve vector<ll> #define dos pair<ll,ll> #define vedos vector<dos> #define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define EPS 0.000001 struct greateri { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } typedef tree< pair<int,dos>, null_type, less<pair<int,dos>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree< dos, null_type, less<dos>, rb_tree_tag, tree_order_statistics_node_update> kalo; kalo X1; ordered_set X; int p[100001]; int seg[1000001]; set<pair<dos,int>>ko,zo; void update(int p,int l,int r,int index,int val){ if(l==r && l==index){ seg[p]=val; return; } ll med=(l+r)>>1; if(index<=med) update(p*2,l,med,index,val); else update(p*2+1,med+1,r,index,val); seg[p]=max(seg[p*2],seg[p*2+1]); } int query(int p,int l,int r,int l1,int r1){ if(l>=l1 && r<=r1){ return seg[p]; } if(l>r || l>r1 || l1>r)return -INF; ll med=(l+r)>>1; return max(query(p*2,l,med,l1,r1),query(p*2+1,med+1,r,l1,r1)); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { flash; vedos prep; set<pair<int,dos>>cii; for (int i = 0; i < N; ++i) { p[i]=i; X1.insert({i,i}); } int in=0; for (int i = 0; i < C; ++i) { ll l=S[i],r=E[i]; ll yo=INF,zo=-1; for (int j = r; j >= l; --j) { in++; auto u=X1.find_by_order(j); auto val=(*u); yo=min(yo,val.first); zo=max(zo,val.second); X1.erase(u); } X1.insert({yo,zo}); prep.pb({yo,zo}); } int ini=0; for(auto it:prep){ ko.insert({{it.first,it.second},ini}); zo.insert({{it.second,it.first},ini}); ini++; } for (int i = 0; i < N-1; ++i) { update(1,0,N*2-1,i*2,K[i]); update(1,0,N*2-1,i*2+1,-INF); } ve cur; dos best={-INF,0}; int index=0; for(auto it:prep){ if(0>=it.first && 0<=it.second){ cur.pb(index); auto f=ko.lower_bound({{it.first,it.second},-INF}); X.insert({(*f).second,(*f).first}); } index++; } int l=0,r=sz(cur)-1; ll ans=-1; while(l<=r){ ll med=(l+r)>>1; auto u=prep[cur[med]]; auto zel=0; if(u.first==0){ zel=max(query(1,0,N*2-1,u.first*2,(u.second)*2-1),R); } if(zel==R){ ans=med+1; l=med+1; } else r=med-1; } if(ans==-1)ans=0; if(best.first<ans) best=max(best,{ans,0}); for (int i = 1; i < N; ++i) { auto v=ko.lower_bound({{i,-INF},-INF}); while(v!=ko.end() && (*v).first.first==i){ X.insert({(*v).second,(*v).first}); v++; } update(1,0,N*2-1,(i-1)*2+1,R); if(i>1)update(1,0,N*2-1,(i-2)*2+1,-INF); index=0; l=0,r=sz(X)-1; ans=-1; while(l<=r){ ll med=(l+r)>>1; auto lo=X.find_by_order(med); auto u=(*lo).second; //u=prep[cur[med]]; auto zel=0; if(i>u.first && i<=u.second){ zel=query(1,0,N*2-1,u.first*2,(u.second)*2-1); } else if(i==u.first){ zel=query(1,0,N*2-1,(u.first-1)*2+1,(u.second)*2-1); } if(zel==R){ ans=med+1; l=med+1; } else r=med-1; } if(ans==-1)ans=0; if(best.first<ans) best=max(best,{ans,i}); auto l=zo.lower_bound({{i,-INF},-INF}); while(l!=zo.end() && (*l).first.first==i){ X.erase({(*l).second,{(*l).first.second,(*l).first.first}}); l++; } } return best.second; }

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp:8: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("O3")
      | 
tournament.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("unroll-loops")
      | 
tournament.cpp: In function 'void setIO(std::string)':
tournament.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tournament.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...