제출 #481834

#제출 시각아이디문제언어결과실행 시간메모리
481834Haruto810198마상시합 토너먼트 (IOI12_tournament)C++17
0 / 100
27 ms8264 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define double long double #define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int, int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair #define lsb(x) ((x)&(-(x))) const int INF = 2147483647; //const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; const int MAX = 100010; int BIT[MAX]; int n; pii seg[MAX]; int seg_r[MAX]; vi edge[MAX]; int Max[MAX][20]; void modify(int pos, int val){ while(pos <= n){ BIT[pos] += val; pos += lsb(pos); } } int Find(int val){ // find smallest x s.t. pref[x] >= val int pos = 0; int sum = 0; for(int j = 19; j >= 0; j--){ if(pos + (1<<j) <= n and sum + BIT[pos + (1<<j)] < val){ sum += BIT[pos + (1<<j)]; pos += (1<<j); } } return pos + 1; } int query_max(int ql, int qr){ if(ql > qr) return -1; int rk = __lg(qr - ql + 1); return max(Max[ql][rk], Max[qr - (1<<rk) + 1][rk]); } int GetBestPosition(int N, int C, int R, int *K, int *st, int *ed){ n = N; // BIT FOR(i, 1, n, 1){ modify(i, 1); seg_r[i] = i; } // s, e: 0 -> 1 FOR(i, 0, C-1, 1){ st[i]++, ed[i]++; seg[i].F = Find(st[i]) - 1; // 1 -> 0 seg[i].S = seg_r[ Find(ed[i]) ] - 1; seg_r[ Find(st[i]) ] = seg_r[ Find(ed[i]) ]; FOR(j, 1, ed[i] - st[i], 1){ modify(st[i] + 1, -1); } } //cerr<<"segments : "<<endl; FOR(i, 0, C-1, 1){ //cerr<<seg[i].F<<" "<<seg[i].S<<endl; } // sparse table FOR(i, 0, n-2, 1){ Max[i][0] = K[i]; } FOR(j, 1, 19, 1){ FOR(i, 0, n-2, 1){ if(i + (1<<(j-1)) <= n-2) Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]); else Max[i][j] = Max[i][j-1]; } } // win condition vector<pii> ev; // pos, val FOR(i, 0, C-1, 1){ // win[l, r]: R at[l, r] and R > arr[l] ... arr[r - 1] if(R > query_max(seg[i].F, seg[i].S - 1)){ ev.eb(seg[i].F, 1); ev.eb(seg[i].S + 1, -1); //cerr<<"win "<<seg[i].F<<" "<<seg[i].S<<endl; } } sort(ev.begin(), ev.end()); int res_max = 0, res_id = 0, cur = 0; for(pii i : ev){ cur += i.S; if(cur > res_max){ res_max = cur; res_id = i.F; } //cerr<<i.F<<" "<<i.S<<endl; } return res_id; }

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

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:100:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |             if(i + (1<<(j-1)) <= n-2) Max[i][j] = max(Max[i][j-1], Max[i + (1<<j-1)][j-1]);
      |                                                                                ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...