Submission #382751

#TimeUsernameProblemLanguageResultExecution timeMemory
382751mehrdad_sohrabiJousting tournament (IOI12_tournament)C++14
0 / 100
124 ms29784 KiB
#include <bits/stdc++.h> /// 500 485 462 A4 using namespace std; typedef long long int ll; typedef complex<double> point; typedef long double ld; #define pb push_back #define pii pair < ll , ll > #define F first #define S second //#define endl '\n' //#define int long long #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #define kill(x) return cout<<x<<'\n', 0; #define inbuf_len 1 << 16 #define outbuf_len 1 << 16 const int MAXN=2e5+100,M=20; ll fen[MAXN]; ll par[MAXN][M]; void add(ll idx,ll val){ for (;idx<MAXN;idx+= idx & (-idx)){ fen[idx]+=val; } } ll getsum(ll idx){ ll s=0; for (;idx;idx-= idx & (-idx)){ s+=fen[idx]; } return s; } ll getk(ll k){ ll l=-1,r=MAXN-1; while(r-l>1){ ll mid=(r+l)/2; if (getsum(mid)>=k) r=mid; else l=mid; } return r; } pii baze[MAXN]; vector <int> g[MAXN]; ll seg[MAXN*4]; void upd(ll nod,ll l,ll r,ll id,ll val){ if (r-l==1){ seg[nod]=val; return ; } ll mid=(r+l)/2; if (mid>id) upd(nod*2,l,mid,id,val); else upd(nod*2+1,mid,r,id,val); seg[nod]=max(seg[nod*2],seg[nod*2+1]); } ll get(ll nod,ll l,ll r,ll L,ll R){ if (l>=R || L>=r) return 0; if (l>=L && r<=R) return seg[nod]; ll mid=(r+l)/2; return max(get(nod*2+1,mid,r,L,R),get(nod*2,l,mid,L,R)); } vector <pii> b; pii baz[MAXN]; ll getpar(ll v,ll h){ for (int i=0;i<M;i++){ if ((h & (1<<i))) v=par[v][i]; } return v; } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){ set <int> s; for (int i=1;i<=N;i++){ s.insert(i); baze[i]={i,i}; add(i,1); } for (int i=0;i<C;i++){ S[i]++; E[i]++; ll l=getk(S[i]); ll r=getk(E[i]); baze[l].S=baze[r].S; b.pb({baze[l].F,baze[l].S}); while(true){ auto t=s.upper_bound(l); if (t==s.end()) break; if (*t>r) break; add(*t,-1); s.erase(t); } } sort(b.begin(),b.end()); // for (auto u : b){ // cout << u.F << " rth " << u.S << endl; //} // return 0; vector <pair <pii,int> > a; for (int i=1;i<=N;i++){ a.pb({{i,-i},i}); baz[i]={i,i}; } for (int i=0;i<b.size();i++){ a.pb({{b[i].F,-b[i].S},i+N+1}); baz[i+N+1]=b[i]; } a.pb({{0,-N*2},0}); sort(a.begin(),a.end()); vector <int> agh; agh.pb(0); for (int i=1;i<a.size();i++){ // cout << i << endl; while(-a[agh.back()].F.S<-a[i].F.S){ agh.pop_back(); } par[a[i].S][0]=a[agh.back()].S; // cout << a[i].S << " " << a[i].F.F << " " << a[i].F.S << " " << par[a[i].S][0] << endl; agh.pb(i); } // return 0; for (int i=0;i<N*2;i++){ for (int j=1;j<M;j++){ par[i][j]=par[par[i][j-1]][j-1]; } } for (int i=1;i<N;i++){ upd(1,1,N,i,K[i-1]); } ll mx=0,ans=0; for (int i=1;i<=N;i++){ ll v=i; ll cnt=0; for (int i=M-1;i>-1;i--){ ll u=par[v][i]; if (u==0) continue; ll l=baz[u].F,r=baz[u].S; ll w=get(1,1,N,l,r); if (w<R){ //cout << v << " " << u << " " << w << endl; v=u; cnt+=(1<<i); } } if (cnt>mx){ ans=i-1; mx=cnt; } } // cout << mx << endl; return ans; } /* int main() { int tmp; char *inbuf, *outbuf; inbuf = (char*) malloc(inbuf_len * sizeof(char)); outbuf = (char*) malloc(outbuf_len * sizeof(char)); tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len); assert(tmp == 0); tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len); assert(tmp == 0); int N, C, R; int *K, *S, *E; tmp = scanf("%d %d %d", &N, &C, &R); assert(tmp == 3); K = (int*) malloc((N-1) * sizeof(int)); S = (int*) malloc(C * sizeof(int)); E = (int*) malloc(C * sizeof(int)); int i; for (i = 0; i < N-1; i++) { tmp = scanf("%d", &K[i]); assert(tmp == 1); } for (i = 0; i < C; i++) { tmp = scanf("%d %d", &S[i], &E[i]); assert(tmp == 2); } printf("%d\n", GetBestPosition(N, C, R, K, S, E)); return 0; } 5 3 3 1 0 2 4 1 3 0 1 0 1 */

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i=0;i<b.size();i++){
      |                  ~^~~~~~~~~
tournament.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=1;i<a.size();i++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...