#include <bits/stdc++.h>
//#define DEBUG 1106
//#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif
using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;
struct node {
int s, e, m, v;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, v = inf;
m = (s+e)/2;
if(s != e) {
l = new node(s, m);
r = new node(m+1, e);
}
}
int query(int a, int b) {
if(a <= s && e <= b) return v;
else if(a > m) return r->query(a, b);
else if(b <= m) return l->query(a, b);
else return min(l->query(a, b), r->query(a, b));
}
void up(int p, int val) {
if(s == e) {
v = val; return;
} else if(p <= m) l->up(p, val);
else r->up(p, val);
v = min(l->v, r->v);
}
} *root;
struct node2 {
int s, e, m, v;
int lazy; //lazy value storage
node2 *l, *r;
node2(int _s, int _e) {
s = _s;
e = _e;
v = lazy = 0;
if (s == e) return;
m = (s + e) / 2;
//Do not create the children here
l = r = nullptr;
}
void chode() {
if (s != e && l == nullptr) {
l = new node2(s, m);
r = new node2(m+1, e);
}
}
void propo() {
//Create before propo
chode();
if (lazy != 0) {
//Update value base on range
v += lazy * (e - s + 1);
//Propogate
if (s != e) {
r -> lazy += lazy;
l -> lazy += lazy;
}
lazy = 0;
}
}
void up(int x, int y, int c) {
chode();
//Propo before update
if (s >= x && e <= y) {
lazy += c;
return;
} else {
propo();
if (y <= m) l -> up(x, y, c);
else if (x > m) r -> up(x, y, c);
else {
l -> up(x, y, c);
r -> up(x, y, c);
}
//Reminder to propo before updating cur node2 value
l -> propo(); r -> propo();
v = l -> v + r -> v;
}
}
int query(int x, int y) {
propo();
if (s >= x && e <= y) return v;
if (x > m) return r -> query(x, y);
if (y <= m) return l -> query(x, y);
else return l -> query(x, y) + r -> query(x, y);
}
int search(int x) {
if (s==e) return s;
chode();
if (l->v>=x) return l->search(x);
else return r->search(x-(l->v));
}
} *root2;
int a[N];
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e) {
root = new node(0,n-1);
root2 = new node2(0,n-1);
forn1(i,n-1) {
a[i] = k[i];
root->up(i,a[i]);
}
a[0]=r;
root->up(0,a[0]);
root2->up(0,n-1,1);
int ans = 0;
int val = -1;
forn(i,n) {
if(i) {
swap(a[i],a[i-1]);
root->up(i,a[i]);
root->up(i-1,a[i-1]);
}
int loc = i;
int rd = 0;
forn(j,c) {
int st = root2->search(s[i]);
int ed = root2->search(e[i]);
int win = root->query(st,ed);
if(st<=loc && loc<=ed) {
rd++;
if(r<=win) break;
loc = st;
root2->up(st,ed,-1);
root2->up(st,st,1);
} else {
if(ed<loc) loc -= (ed-st);
}
}
if(rd>val) ans = i, val = rd;
}
return ans;
}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
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;
}
*/
Compilation message
tournament.cpp:30:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
30 | const int INF = 1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1057 ms |
6236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
