| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1258623 | daotuankhoi | Jousting tournament (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }
/**
Thay vi viec ta dat thg n o vi tri nao do roi kiem tra xem no thang duoc bao nhieu tran
voi do phuc tap O(n^2) thi ta se tinh dap an cho tat ca cac vi tri co the dat
trong 1 lan.
Cac vi tri co the dat thg n:
slot_0 rank(1) slot_1 rank(2) ... slot_n-2 rank(n - 1) slot_n-1 (n vi tri dat)
Cac slot nam xen ke giua 2 thg ban dau
Goi cnt[i] = so tran thang khi dat thg r o slot thu i
Ta bieu dien cac thg ban dau va cac tran dau duoi dang cay
Cac la la cac thg ban dau
Khi xet den tran thu i, co canh noi tu i den tat ca cac dinh tu l -> r sau khi nen lai
(Khi xong 1 tran, doan [l, r] se nen lai thanh 1 phan tu
Gia su trong cay con goc u quan ly cac dau si tu [l -> r]
Thi doan nay anh huong den cac slot tu [l -> r - 1] (ly do vi khi ta nhet thg r vao 1 trong
cac vi tri tu l -> r - 1, thang cuoi cung
se bi day ra khoi doan, khien no khong anh
huong gi den cac slot tu l -> r - 1)
=> Doan ma cay con goc u anh huong la [l, r)
Khi ta duyet tu con v1 -> v2, doan no se la [l1, r1) + [l2, r2) nhung ban chat khi r1 bi day ra
nhung no van nam trong doan anh huong, the nen ta phai cong ca dong gop cua r1 (r1 + 1 = l2)
Vi tong tat ca (ri - li + 1) = n nen ta for trau l -> r
**/
const int MAXN = 2e5 + 5;
int id[MAXN];
int n, m, late;
int rk[MAXN];
vector<int> g[MAXN];
int curLeaf = 0; /// vi cac la bieu dien tu 0 -> n - 1 nen ta duy tri chi so la hien tai
int dfs(int u) {
if (u == 0) {
curLeaf++;
/// [l, l) la doan rong nen no se khong co dong gop gi
return -1;
}
int s = curLeaf, mx = -1;
for (int v : g[u]) {
ckmax(mx, dfs(v));
if (v != g[u].back()) /// khi khong bi day ra khoi doan, cong them dong gop cua thg cuoi vao
ckmax(mx, rk[curLeaf]);
}
if (late > mx) {
id[s]++;
id[curLeaf]--;
/// curLeaf tai thoi diem nay la diem cuoi cua doan [l, r), khong dong gop vao dap an
}
return mx;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> late;
for (int i = 1; i < n; i++) {
cin >> rk[i];
}
for (int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
for (int j = l; j <= r; j++) {
g[i].emplace_back(id[j]);
id[j] = 0;
}
id[l] = i;
}
memset(id, 0, sizeof id);
dfs(m);
curLeaf = 0;
for (int i = 0; i < n; i++) {
id[i + 1] += id[i];
if (id[curLeaf] < id[i]) curLeaf = i;
}
cout << curLeaf;
return 0;
}