| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 414789 | Lam_lai_cuoc_doi | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
constexpr bool typetest = 0;
constexpr int N = 2e5 + 5;
struct FenwickTree
{
int a[N];
int n;
FenwickTree()
{
memset(a, 0, sizeof a);
}
void Update(int p, int v)
{
for (; p <= n; p += p & -p)
a[p] += v;
}
int Get(int p)
{
int ans(0);
for (; p; p -= p & -p)
ans += a[p];
return ans;
}
int Get(int l, int r)
{
return Get(r) - Get(l - 1);
}
} g;
struct Segmentree
{
int st[N * 4], lazy[N * 4];
void Build(int id, int l, int r)
{
if (l == r)
{
st[id] = 1;
lazy[id] = -1;
return;
}
Build(id << 1, l, (l + r) / 2);
Build(id << 1 | 1, (l + r) / 2 + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
lazy[id] = -1;
}
void Push(int id, int l, int r)
{
if (lazy[id] != -1)
{
int mid = (l + r) / 2;
st[id << 1] = (mid - l + 1) * lazy[id];
lazy[id << 1] = lazy[id];
st[id << 1 | 1] = (r - mid) * lazy[id];
lazy[id << 1 | 1] = lazy[id];
lazy[id] = -1;
}
}
void Update(int id, int l, int r, const int &a, const int &b, const int &v)
{
if (l > b || r < a)
return;
if (l >= a && r <= b)
{
st[id] = (r - l + 1) * v;
lazy[id] = v;
return;
}
Push(id, l, r);
Update(id << 1, l, (l + r) / 2, a, b, v);
Update(id << 1 | 1, (l + r) / 2 + 1, r, a, b, v);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int Find(int id, int l, int r, int v)
{
while (1)
{
if (l == r)
return l;
Push(id, l, r);
if (st[id << 1] >= v)
{
id <<= 1;
r = (l + r) / 2;
}
else
{
v -= st[id << 1];
id = id << 1 | 1;
l = (l + r) / 2 + 1;
}
}
return 0;
}
} f;
int last[N], id[N];
int GetBestPosition(int n, int c, int r, int *k, int *s, int *e)
{
f.Build(1, 1, n);
g.n = n;
for (int i = 1; i <= n; ++i)
last[i] = i;
for (int i = 0; i < c; ++i)
{
*(s + i) = f.Find(1, 1, n, ++*(s + i));
*(e + i) = last[f.Find(1, 1, n, ++*(e + i))];
//cout << *(s + i) << " " << *(e + i) << "\n";
last[*(s + i)] = *(e + i);
f.Update(1, 1, n, *(s + i) + 1, *(e + i), 0);
id[i] = i;
}
sort(id, id + c, [&](const int &x, const int &y)
{ return *(s + x) < *(s + y) || (*(s + x) == *(s + y) && *(e + x) < *(e + y)); });
int z = c - 1;
priority_queue<pair<int, int>> x;
for (int i = 0, j = 0; i < n - 1; ++i)
{
while (j < n - 1 && (k[i] <= r) == (k[j] <= r))
++j;
if (k[i] <= r)
{
while (~z && *(s + id[z]) >= i + 1)
{
x.emplace(*(e + id[z]), *(s + id[z]));
--z;
}
while (x.size() && x.top().first > j + 1)
x.pop();
while (x.size())
{
//cout << x.top().second << " " << x.top().first << "\n";
g.Update(x.top().second, 1);
g.Update(x.top().first + 1, -1);
x.pop();
}
}
i = j - 1;
}
pair<int, int> u = {0, 0};
for (int i = 1; i <= n; ++i)
u = max(u, make_pair(g.Get(i), -(i - 1)));
return -u.second;
}