| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 745345 | finn__ | Teams (IOI15_teams) | 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.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,sse4")
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T, int64_t N, int64_t M>
struct FenwickTree2dOff
{
T t[M];
vector<pair<unsigned, unsigned>> coords;
unsigned b[N + 1], c[M];
void add_coordinate(int64_t i, int64_t j) { coords.emplace_back(i, j); }
void initialize()
{
sort(coords.begin(), coords.end(), [](auto const &a, auto const &b)
{ return a.second < b.second; });
memset(t, 255, N * sizeof *t);
for (auto const &[x, y] : coords)
for (int64_t i = x + 1; i <= N; i += i & -i)
b[i - 1] += (t[i - 1] != y), t[i - 1] = y;
for (size_t i = 1; i < N; ++i)
b[i] += b[i - 1];
memset(t, 255, N * sizeof *t);
for (auto const &[x, y] : views::reverse(coords))
for (int64_t i = x + 1; i <= N; i += i & -i)
if (t[i - 1] != y)
c[--b[i - 1]] = y, t[i - 1] = y;
memset(t, 0, N * sizeof *t);
}
void update(int64_t i, int64_t j, T x)
{
++i;
while (i <= N)
{
int64_t k = upper_bound(c + b[i - 1], c + b[i], j) - (c + b[i - 1]);
while (k <= b[i] - b[i - 1])
t[b[i - 1] + k - 1] += x, k += k & -k;
i += i & -i;
}
}
T prefix_sum(int64_t i, int64_t j)
{
++i;
T x = 0;
while (i)
{
int64_t k = upper_bound(c + b[i - 1], c + b[i], j) - (c + b[i - 1]);
while (k)
x += t[b[i - 1] + k - 1], k -= k & -k;
i -= i & -i;
}
return x;
}
T range_sum(int64_t i1, int64_t i2, int64_t j1, int64_t j2)
{
return prefix_sum(i2, j2) - (i1 ? prefix_sum(i1 - 1, j2) : 0) -
(j1 ? prefix_sum(i2, j1 - 1) : 0) +
(i1 && j1 ? prefix_sum(i1 - 1, j1 - 1) : 0);
}
};
constexpr size_t MaxN = 500009, Block = 500, TreeSize = 1000000;
FenwickTree2dOff<int, MaxN, TreeSize> tree;
size_t n;
pair<int, int> pupils[MaxN];
void init(int N, int A[], int B[])
{
for (size_t i = 0; i < N; ++i)
tree.add_coordinate(A[i], B[i]), pupils[i] = {A[i], B[i]};
tree.initialize();
for (size_t i = 0; i < N; ++i)
tree.update(A[i], B[i], 1);
n = N;
sort(pupils, pupils + n);
}
int can(int M, int K[])
{
sort(K, K + M);
if (M <= Block)
{
size_t j = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (size_t i = 0; i < M; ++i)
{
while (j < n && pupils[j].first <= K[i])
q.emplace(pupils[j].second, pupils[j].first), ++j;
while (!q.empty() && q.top().first < K[i])
q.pop();
if (q.size() < K[i])
return 0;
while (K[i]--)
q.pop();
}
}
else
{
vector<int64_t> f(M);
for (size_t i = 0; i < M; ++i)
{
f[i] = tree.range_sum(0, K[i], K[i], MaxN - 1) - K[i];
for (size_t j = 0; j < i && f[i] >= 0; ++j)
f[i] = min(f[i], f[j] + (K[i] == K[j] ? 0 : tree.range_sum(K[j] + 1, K[i], K[i], MaxN - 1)) - K[i]);
if (f[i] < 0)
return 0;
}
}
return 1;
}