| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 284501 | nvmdava | 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.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const int N = 500005;
struct Node{
int s;
Node *L, *R;
Node(int _s, Node *_L, Node *_R){
s = _s; L = _L; R = _R;
}
int query(int l, int r, int le, int ri){
if(le > r || ri < l) return 0;
if(le <= l && r <= ri) return s;
int m = (l + r) >> 1;
return L -> query(l, m, le, ri) + R -> query(m + 1, r, le, ri);
}
Node* update(int l, int r, int x){
if(l > x || r < x) return this;
if(l == r) return new Node(s + 1, L, R);
int m = (l + r) >> 1;
return new Node(s + 1, L -> update(l, m, x), R -> update(m + 1, r, x));
}
void build(int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
L = new Node(0, NULL, NULL);
R = new Node(0, NULL, NULL);
L -> build(l, m);
R -> build(m + 1, r);
}
};
vector<int> lol[N];
Node* tree[N];
int query(int x1, int y1, int x2, int y2){
--y1;
return tree[y2] -> query(1, N, x1, x2) - tree[y1] -> query(1, N, x1, x2);
}
void init(int n, int A[], int B[]) {
for(int i = 0; i < n; ++i)
lol[B[i]].push_back(A[i]);
tree[0] = new Node(0, NULL, NULL);
tree[0] -> build(1, N);
for(int i = 1; i < N; ++i){
tree[i] = tree[i - 1];
for(auto& x : lol[i]){
tree[i] = tree[i] -> update(1, N, x);
}
}
}
vector<pair<int, int> > val;
vector<pair<int, pair<int, int> > > kill;
int can(int M, int K[]) {
sort(K + 0, K + M);
val.clear();
for(int i = 0; i < M; ++i){
if(val.empty() || val.back().ff != K[i])
val.push_back({K[i], 0});
val.back().ss += K[i];
if(val.back().ss > N) return 0;
}
M = val.size();
val.push_back({N, 0});
kill = {{1, {M, 0}}};
for(int i = 0; i < M; ++i){
while(kill.back().ss.ff < i)
kill.pop_back();
while(kill.back().ss.ff == i){
val[i].ss += kill.back().ss.ss;
kill.pop_back();
if(val[i].ss > N) return 0;
}
int s, br = i;
while((s = query(kill.back().ff, val[br].ff, val[i].ff, val[kill.back().ss.ff].ff - 1)) <= val[i].ss){
val[i].ss -= s;
br = kill.back().ss.ff;
val[i].ss += kill.back().ss.ss;
kill.pop_back();
if(kill.empty()){
if(i == M - 1 && val[i].ss == 0)
return 1;
return 0;
}
}
for(int j = 20; j >= 0; --j){
if(br + (1 << j) <= kill.back().ss.ff && (s = query(kill.back().ff, val[br].ff, val[i].ff, val[br + (1 << j)].ff - 1)) <= val[i].ss){
val[i].ss -= s;
br += 1 << j;
}
}
kill.push_back({val[i].ff + 1, {br, val[i].ss}});
}
return 1;
}