| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1065861 | ArthuroWich | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "tournament.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
struct node {
int p = -1, v = INT_MIN, w = 0;
vector<int> c = {};
};
node t[300005];
int timer, ra, v = 0;
void calc(int i) {
for (int j : t[i].c) {
calc(j);
}
for (int j : t[i].c) {
t[i].v = max(t[i].v, t[j].v);
}
}
void update(int i) {
for (int j : t[i].c) {
t[i].v = max(t[i].v, t[j].v);
}
if (t[i].p != -1) {
update(t[i].p);
}
}
void trav(int i) {
if (t[i].w && t[i].v == ra) {
v++;
}
if (t[i].v != ra) {
return;
}
if (t[i].p) {
trav(t[i].p);
}
}
int GetBestPosition(int n, int m, int r, int k[], int S[], int E[]) {
ra = r;
indexed_set e;
timer = n;
int ans = 0, ind = -1;
for (int i = 0; i < n; i++) {
e.insert({i, i});
}
t[0].v = r;
for (int i = 0; i < n-1; i++) {
t[i+1].v = k[i];
}
for (int i = 0; i < m; i++) {
int le = E[i]-S[i]+1;
set<pair<int, int>> todel;
pair<int, int> c = {S[i], INT_MIN};
auto ind = e.find_by_order(e.order_of_key(c));
int l = INT_MAX;
while(le--) {
c = *ind;
todel.insert(c);
l = min(l, c.first);
t[timer].c.push_back(c.second);
t[c.second].p = timer;
t[timer].w = 1;
ind++;
}
for (auto c : todel) {
e.erase(c);
}
e.insert({l, timer});
timer++;
}
int root = timer-1;
calc(root);
trav(0);
ans = v;
ind = 0;
for (int i = 1; i < n; i++) {
swap(t[i-1].v, t[i].v);
update(i-1);
update(i);
v = 0;
trav(i);
if (v > ans) {
ans = v;
ind = i;
}
}
return ind;
}