| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1212990 | Lemser | Teams (IOI15_teams) | C++20 | 0 ms | 0 KiB |
#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }
const int N = 5e5 + 7;
const int MAX = 15000000;
int snd[MAX], leftnd[MAX], rightnd[MAX];
int n, rts[N], act_idx, dp[1005];
vector<int> ps[N], ot[N];
int new_node (int l, int r) {
int x = act_idx++;
snd[x] = 0;
leftnd[x] = -1;
rightnd[x] = -1;
return x;
}
int update (int id, int l, int r, int i, int v){
if (r<i || l>i) return id;
auto t = new_node(l, r);
int m = (l+r)/2;
if (l == r) snd[t] = snd[id]+v;
else{
leftnd[t] = update(leftnd[id], l, m, i, v);
rightnd[t] = update(rightnd[id], m+1, r, i,v);
snd[t] = snd[leftnd[t]] + snd[rightnd[t]];
}
return t;
}
int query (int id, int l, int r, int i, int j){
if (l>j || r<i) return 0;
if (l>=i && r<=j) return snd[id];
return query(leftnd[id], l, (l+r)/2, i, j) + query(rightnd[id], (l+r+2)/2, r, i,j);
}
void constr (int id, int l, int r) {
if (l == r) return;
int m = (l+r)/2;
leftnd[id] = new_node(l, m);
rightnd[id] = new_node(m+1, r);
constr(leftnd[id], l, m);
constr(rightnd[id], m+1, r);
}
void init(int N, int a[], int b[]) {
act_idx = 0;
n = N;
rts[n+1] = new_node(1, n);
constr(rts[n+1], 1, n);
fo (i, n) ps[a[i]].pb(b[i]);
fo (i, n) ot[b[i]].pb(a[i]);
forex (x, n+1, 1) {
rts[x] = update(rts[x+1], 1, n, 0, 0);
for (int y: ot[x]) {
rts[x] = update(rts[x], 1, n, y, +1);
}
}
}
int can(int m, int k[]) {
sort(k, k+m);
if (accumulate(k, k+m, 0ll) > n) return 0;
if (m >= 500) {
int r = 1;
priority_queue<ll, greater<ll>, vll> pq;
fo (i, m) {
while (r <= k[i]) {
for (int b: ps[r])
pq.push(b);
r++;
}
while (pq.size() && pq.top() < k[i]) pq.pop();
while (pq.size() && k[i]--) pq.pop();
if (k[i] > 0) return 0;
}
return 1;
}
fo (i, m) {
// no elegir a nadie
int r = query(rts[k[i]], 1, n, 1, k[i]);
dp[i] = r;
fo (j, i) {
if (k[i] != k[j]) r = query(rts[k[i]], 1, n, k[j]+1, k[i]);
else r = 0;
dp[i] = min(dp[i], dp[j] + r);
}
dp[i] -= k[i];
if (dp[i] < 0) return 0;
}
return 1;
}