| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 419262 | arayi | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "tournament.h"
#include <iostream>
#include <vector>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
#define pir pair<int, int>
using namespace std;
const int N = 1e6 + 30;
int n, m;
int l[N], r[N], a[N];
int t[4 * N];
pir flg[4 * N];
void push(int nd)
{
if (flg[nd].fr > 0)
{
t[nd] = flg[nd].fr + flg[nd].sc;
flg[nd * 2] = flg[nd * 2 + 1] = flg[nd];
flg[nd] = MP(0, 0);
}
else
{
t[nd] += flg[nd].sc;
flg[nd * 2].sc += flg[nd].sc;
flg[nd * 2 + 1].sc += flg[nd].sc;
flg[nd].sc = 0;
}
}
void upd(int l, int r, int v, int nl = 1, int nr = n, int nd = 1)
{
push(nd);
if (l > nr || r < nl) return;
if (l == nl && r == nr)
{
if (v > 0) flg[nd] = MP(v, 0);
else flg[nd].sc += v;
push(nd);
return;
}
int mid = (nl + nr) / 2;
upd(l, min(mid, r), v, nl, mid, nd * 2);
upd(max(mid + 1, l), r, v, mid + 1, nr, nd * 2 + 1);
t[nd] = min(t[nd * 2], t[nd * 2 + 1]);
}
int qry(int v, int l = 1, int r = n, int nd = 1)
{
push(nd);
if (l == r)
{
if (t[nd] > v) return l - 1;
return l;
}
push(nd * 2);
push(nd * 2 + 1);
int mid = (l + r) / 2;
if (t[nd * 2 + 1] <= v) return qry(v, mid + 1, r, nd * 2 + 1);
else return qry(v, l, mid, nd * 2);
}
int qr(int q, int l = 1, int r = n, int nd = 1)
{
push(nd);
if (l > q || r < q) return 0;
if (l == r) return t[nd];
int mid = (l + r) / 2;
return qr(q, l, mid, nd * 2) + qr(q, mid + 1, r, nd * 2 + 1);
}
void bld(int l = 0, int r = n - 2, int nd = 1)
{
if (l == r)
{
t[nd] = a[l];
return;
}
int mid = (l + r) / 2;
bld(l, mid, nd * 2);
bld(mid + 1, r, nd * 2 + 1);
t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
int qry1(int l, int r, int nl = 0, int nr = n - 2, int nd = 1)
{
if (l > nr || r < nl) return 0;
if (l == nl && r == nr) return t[nd];
int mid = (nl + nr) / 2;
return max(qry1(l, min(mid, r), nl, mid, nd * 2), qry1(max(mid + 1, l), r, mid + 1, nr, nd * 2 + 1));
}
int fp[N];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n = N, m = C;
for (int i = 1; i <= n; i++) upd(i, i, i);
for (int i = 0; i < n - 1; i++) a[i] = K[i];
for (int i = 0; i < m; i++)
{
S[i]++, E[i]++;
int a = qry(S[i] - 1) + 1, b = qry(E[i]);
l[i] = a - 1, r[i] = b - 1;
upd(a, b, S[i]);
upd(b + 1, n, S[i] - E[i]);
S[i]--, E[i]--;
}
bld();
for (int i = 0; i < m; i++)
{
int sm = qry1(l[i], r[i] - 1);
//cout << l[i] << " " << r[i] << " " << sm << endl;
if (sm < R) fp[l[i]]++, fp[r[i] + 1]--;
}
int i1 = 0;
for (int i = 1; i < n; i++)
{
fp[i] += fp[i - 1];
if (fp[i] > fp[i1]) i1 = i;
}
return i1;
}