제출 #282719

#제출 시각아이디문제언어결과실행 시간메모리
282719youssefbou62마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
1087 ms2552 KiB
#include <bits/stdc++.h> using namespace std; // using namespace __gnu_pbds; #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define mp make_pair #define fi first #define se second #define all(v) v.begin(),v.end() #define allarr(a) a , a + n #define ll long long #define ull unsigned long long #define pb push_back #define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL) #define sz(x) (int)x.size() typedef pair<int, int> pi; typedef pair<ll,ll> pll; typedef pair<int,pi> trp ; typedef vector<pi> vpi; typedef vector<pll> vpll ; // int ab (int x ) { return (x>0?x:-x); } //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int MAXN = 1e5+5; int in[MAXN] , jump[MAXN],best[MAXN]; int st[MAXN*2] , par[MAXN][20]; int v[MAXN]; void init(int n){ for(int i = 0 ; i< n ;i++ ) in[i] = i , jump[i] = i ; } int left(int u){return u*2+1;} int right(int u){return u*2+2;} void build (int i,int j,int in,int u){ if( i > j )return ; if( i == j ){ st[u] = v[in]; return ; } int mid = (i+j)/2; if( in <= mid ) build(i,mid,in,left(u)); else build(mid+1,j,in,right(u)); st[u] = max(st[left(u)],st[right(u)]); } int query(int i,int j,int qL ,int qR,int u){ // if( qL == 1 && qR == 3 )cout << i << " " << j << " " << u << endl; if( i > j || i > qR || j < qL ) return -1; if( i >= qL && j <= qR )return st[u] ; int mid = ( i + j )/2; return max(query(i,mid,qL,qR,left(u)) , query(mid+1,j,qL,qR,right(u))); } int kth_anc(int a,int k){ for(int i = 19 ; i >= 0 ; i-- ){ if( k&(1<<i) ){ k -= (1<<i); a = par[a][i]; } } return a; } vpi queries ; void preprocess(int N, int C, int R, int *K, int *S, int *E){ for(int i = 0 ; i < N-1 ; i++ )v[i] = K[i] ; for(int i = 0 ; i < C ; i++ ){ int s = S[i] , e = E[i] ; int new_index = s ; int L = 1e9 , Rx = -1 ; int last = -1 ; for(int j = 0 ; j < N ; j++ ){ if( in[j] >= s && in[j] <= e){ last = in[j] ; in[j] = new_index; L = min(L,j); Rx = max(Rx,j); } if( in[j] > e && in[j]!=last)new_index ++ ; if( in[j] > e ) last=in[j],in[j] = new_index ; } queries.pb({L,Rx}); } } void process_parents(int N, int C, int R, int *K, int *S, int *E){ for(int i = 0 ; i < sz(queries) ; i++ ){ int l = 0 , r = sz(queries) -1 , in =-1; while ( l <= r ){ int mid = ( l + r )/2; if(queries[mid].fi<=queries[i].fi){ l = mid + 1 ; in = mid ; }else r = mid-1; } par[i][0] = in; } for(int i = sz(queries)-1 ; i >= 0 ; i-- ){ for(int j = 1 ; j <= 19 ; j++ ){ par[i][j] = par[par[i][j-1]][j-1]; } } } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { init(N); preprocess(N,C,R,K,S,E); // reverse(all(queries)); for(int i=N-1;i>=0;i--) queries.pb({i,i}); sort(all(queries)); process_parents(N,C,R,K,S,E); int ans=-1,pos; for(int i = N-1 ; i != -1 ; i-- ){ v[i] = R; build(0,N-1,i,0); int l = 0 , r = N , curr_ans = 0; int inde = lower_bound(all(queries),make_pair(i,i))-queries.begin(); while ( l <= r ){ int mid = (l+r)/2 ; int a = kth_anc(inde,mid); if( a == -1 ){ r = mid-1; }else{ bool ok = (query(0,N-1,queries[a].fi,queries[a].se,0)==R); if( ok ){ l = mid + 1 ; curr_ans = mid ; }else r = mid-1; } } if( curr_ans >= ans ){ ans = curr_ans ; pos = i ; } v[i] = v[i-1] ; build(0,N-1,i,0); } assert(ans!=-1); return pos; } // #define inbuf_len 1 << 16 // #define outbuf_len 1 << 16 // int GetBestPosition(int N, int C, int R, int *K, int *S, int *E); // int main() { // int tmp; // /* Set input and output buffering */ // 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; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...