| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1122463 | Sang | 마상시합 토너먼트 (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define _pbrngw_ Khánh Băng dthw nhất hệ mặt trời :>>
#define int long long
#define ALL(a) (a).begin(), (a).end()
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, r, c, T[4*N][2], v[N], mx[N][20];
ii lazy[4*N], a[N];
void build(int id, int l, int r){
if (l == r) {
T[id][0] = T[id][1] = l;
return;
}
int m = (l+r)/2;
build(id*2, l, m);
build(id*2+1, m+1, r);
T[id][0] = max(T[id*2][0], T[id*2+1][0]);
T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}
void down(int id){
int val1 = lazy[id].fi, val2 = lazy[id].se;
if (val2){
T[id*2][0] = T[id*2+1][0] = val2;
T[id*2][1] = T[id*2+1][1] = val2;
lazy[id*2].se = lazy[id*2+1].se = val2;
lazy[id*2].fi = lazy[id*2+1].fi = 0;
}
T[id*2][0] += val1;
T[id*2+1][0] += val1;
T[id*2][1] += val1;
T[id*2+1][1] += val1;
lazy[id*2].fi += val1;
lazy[id*2+1].fi += val1;
lazy[id] = {0, 0};
}
void update(int id, int l, int r, int u, int v, int val){
if (l > v || r < u) return;
if (u <= l && r <= v){
T[id][0] += val;
T[id][1] += val;
lazy[id].fi += val;
return;
}
int m = (l+r)/2;
down(id);
update(id*2, l, m, u, v, val);
update(id*2+1, m+1, r, u, v, val);
T[id][0] = max(T[id*2][0], T[id*2+1][0]);
T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}
void update2(int id, int l, int r, int u, int v, int val){
if (l > v || r < u) return;
if (u <= l && r <= v){
T[id][0] = T[id][1] = val;
lazy[id] = {0, val};
return;
}
int m = (l+r)/2;
down(id);
update2(id*2, l, m, u, v, val);
update2(id*2+1, m+1, r, u, v, val);
T[id][0] = max(T[id*2][0], T[id*2+1][0]);
T[id][1] = min(T[id*2][1], T[id*2+1][1]);
}
int get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return T[id][0];
down(id);
int m = (l+r)/2;
return max(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
}
int getL(int id, int l, int r, int k){
if (T[id][0] < k) return -1;
if (l == r) return l;
int m = (l+r)/2;
down(id);
int ans = getL(id*2, l, m, k);
if (ans == -1) return getL(id*2+1, m+1, r, k);
return ans;
}
int getR(int id, int l, int r, int k){
if (T[id][1] > k) return -1;
if (l == r) return l;
int m = (l+r)/2;
down(id);
int ans = getR(id*2+1, m+1, r, k);
if (ans == -1) return getR(id*2, l, m, k);
return ans;
}
int getMax(int l, int r){
int k = log2(r-l+1);
return max(mx[l][k], mx[r-(1<<k)+1][k]);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
n = N; c = C; r = R;
FOR (i, 1, n-1) mx[i][0] = K[i - 1];
build(1, 1, n);
FOR (i, 1, c){
int s, e; s = S[i-1]; e = E[i-1];
int L = getL(1, 1, n, s), R = getR(1, 1, n, e) ;
a[i] = {L, R};
// cout << L << ' ' << R << "\n";
update2(1, 1, n, L, R, get(1, 1, n, 1, L-1)+1);
update(1, 1, n, R+1, n, - (e - s));
// cout << get(1, 1, n, 5, 5) << "\n";
}
for (int j = 1; (1<<j) < n; j++){
for (int i = 1; i + (1<<j) - 1 < n; i++){
mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
int ans = 0, pos = 1;
FOR (i, 1, 4*n + 2) lazy[i] = {0, 0}, T[i][0] = T[i][1] = 0;
FOR (i, 1, c){
if (getMax(a[i].fi, a[i].se - 1) < r){
update(1, 1, n, a[i].fi, a[i].se, 1);
} else update(1, 1, n, a[i].fi, a[i].se, -1e9);
if (ans < T[1][0]){
pos = getL(1, 1, n, T[1][0]);
ans = T[1][0];
} else if (ans == T[1][0]) pos = min(pos, getL(1, 1, n, ans));
}
return pos;
}