| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 396397 | peuch | 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 <stdio.h>
#include <stdlib.h>
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10;
int n;
pair<int, int> v[MAXN];
int bank[MAXN];
int m;
int k[MAXN];
vector<int> seg, e, d;
int create();
int copia(int pos);
int update(int pos, int ini, int fim, int id);
int query(int pos, int ini, int fim, int p, int q);
int bb(int pos1, int pos2, int ini, int fim, int val);
void init(int N, int A[], int B[]) {
n = N;
create();
bank[0] = create();
for(int i = 0; i < n; i++)
v[i + 1] = make_pair(A[i], B[i]);
sort(v + 1, v + 1 + n);
for(int i = 1; i <= n; i++)
bank[i] = update(bank[i - 1], 1, n, v[i].second);
}
int can(int M, int K[]) {
m = M;
for(int i = 0; i < m; i++)
k[i + 1] = K[i];
sort(k + 1, k + 1 + m);
stack<pair<int, pair<int, int> > > pilha;
pilha.push(make_pair(MAXN + 10, make_pair(0, 0)));
for(int i = 1; i <= m; i++){
int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN)) - v - 1;
if(j <= 0) return 0;
while(k[i] > pilha.top().first) pilha.pop();
int sum = query(bank[j], 1, n, k[i], k[i]) - query(bank[pilha.top().second.first], 1, n, k[i], k[i]);
int hmin = k[i] + 1;
int hmax = k[i];
while(!pilha.empty()){
if(sum >= k[i]) break;
int it = pilha.top().second.first;
hmax = pilha.top().first;
int diff = query(bank[j], 1, n, hmin, hmax) - query(bank[it], 1, n, hmin, hmax);
if(diff + sum >= k[i]){
int aux = query(bank[j], 1, n, 1, hmin - 1) - query(bank[it], 1, n, 1, hmin - 1);
hmax = bb(bank[j], bank[it], 1, n, k[i] - sum + aux);
diff = query(bank[j], 1, n, hmin, hmax) - query(bank[it], 1, n, hmin, hmax);
sum += diff;
break;
}
else sum += diff + pilha.top().second.second, hmin = hmax + 1, pilha.pop();
}
if(sum < k[i]) return 0;
pilha.push(make_pair(hmax, make_pair(j, sum - k[i])));
}
return 1;
}
int create(){
seg.push_back(0);
e.push_back(0);
d.push_back(0);
return seg.size() - 1;
}
int copia(int pos){
seg.push_back(seg[pos]);
e.push_back(e[pos]);
d.push_back(d[pos]);
return seg.size() - 1;
}
int update(int pos, int ini, int fim, int id){
if(ini > id || fim < id) return pos;
int newNode = copia(pos);
if(ini == fim){
seg[newNode]++;
return newNode;
}
int mid = (ini + fim) >> 1;
int aux = update(e[pos], ini, mid, id);
e[newNode] = aux;
aux = update(d[pos], mid + 1, fim, id);
d[newNode] = aux;
seg[newNode] = seg[e[newNode]] + seg[d[newNode]];
return newNode;
}
int query(int pos, int ini, int fim, int p, int q){
if(ini > q || fim < p) return 0;
if(ini >= p && fim <= q) return seg[pos];
int mid = (ini + fim) >> 1;
return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q);
}
int bb(int pos1, int pos2, int ini, int fim, int val){
if(ini == fim) return ini;
int mid = (ini + fim) >> 1;
if(seg[e[pos1]] - seg[e[pos2]] >= val)
return bb(e[pos1], e[pos2], ini, mid, val);
return bb(d[pos1], d[pos2], mid + 1, fim, val - (seg[e[pos1]] - seg[e[pos2]]));
}
int main() {
int N;
scanf("%d", &N);
int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; ++i) {
scanf("%d %d", &A[i], &B[i]);
}
init(N, A, B);
int Q;
scanf("%d", &Q);
for (int i = 0; i < Q; ++i) {
int M;
scanf("%d", &M);
int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
for (int j = 0; j < M; ++j) {
scanf("%d", &K[j]);
}
printf("%d\n", can(M, K));
}
return 0;
}