| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22020 | sbansalcs | Teams (IOI15_teams) | C++14 | 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 <stack>
#include <math.h>
#include <vector>
//#include <assert.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e5+5;
#define right r
#define left l
#define mid (start+end)/2
struct node2;
struct node {
node *l,*r;
int val;
node() {
l=NULL,r=NULL,val=0;
}
node* build(int start, int end) {
val=0;
if(start!=end) {
l=new node,r=new node,l=l->build(start,mid),r=r->build(mid+1,end);
}
return this;
}
int query(int start, int end, int a, int b) {
if(start>=a && end<=b) return val;
else if(start>b || end<a) return 0;
else return l->query(start,mid,a,b)+r->query(mid+1,end,a,b);
}
node* update(int start, int end, int x, int v) {
node* f=new node;
f->left=left;
f->right=right;
f->val=val+v;
if(start==end) {
return f;
}
else if(x<=mid) {
f->left=left->update(start,mid,x,v);
}
else {
f->right=right->update(mid+1,end,x,v);
}
return f;
}
// int assign(node2* used, int start, int end, int a, int b, int v) {
//// used=used->lz()
// }
};
struct node2
{
node* points;
int val;
node2 *l,*r;
node2* build(int start, int end) {
val=0,points=NULL;
if(start!=end) {
l=new node2,r=new node2;l=l->build(start,mid),r=r->build(mid+1,end);
}
return this;
}
node2* clear(int start, int end) {
if(val!=0 || points!=NULL) {
if(start!=end) l=l->clear(start,mid),r=r->clear(mid+1,end);
}
points=NULL,val=0;
return this;
}
node2* lz(int start, int end) {
if(!points) return this;
val=points->val;
if(start!=end) {
l->points=points->l;
r->points=points->r;
}
points=NULL;
return this;
}
};
node2* used;
int assign(node* rt, node2* &used, int start, int end, int a, int b, int v) {
used=used->lz(start,end);
if(start>b || end<a) return 0;
if(v==0) return 0;
int av =rt->val-used->val;
if(start>=a && end<=b) {
if(av<=v) {
used->points=rt;
used=used->lz(start,end);
return av;
}
else {
int lf=assign(rt->l, used->l, start, mid, a, b, v);
int rf=assign(rt->r, used->r, mid+1, end, a, b, v-lf);
return rf+lf;
}
}
else {
int lf=assign(rt->l, used->l, start, mid, a, b, v);
int rf=assign(rt->r, used->r, mid+1, end, a, b, v-lf);
return rf+lf;
}
}
node* root[N];
int A[N],B[N];
int n;
int del[N];
int sz=0;
int dp[N];
void init(int _n, int a[], int b[]) {
n=_n;
vector<pair<int,int>> vt;
for(int i=1;i<=n;i++) {
A[i]=a[i-1];
B[i]=b[i-1];
vt.push_back({A[i],B[i]});
}
sort(vt.begin(),vt.end());
root[0]=new node;root[0]=root[0]->build(1,n);
int preve=0;
for(int i=0;i<n;i++) {
while(preve+1<vt[i].first) {
root[preve+1]=root[preve];
preve++;
}
root[vt[i].first]=root[preve]->update(1,n,vt[i].second,1);
// assert(vt[i].first-preve<=1);
preve=vt[i].first;
}
for(int i=preve+1;i<=n;i++) {
root[i]=root[i-1];
}
used=new node2;
used=used->build(1, n);
}
int getCount(int a, int b) {
int h=root[b]->query(1,n,b,n)-root[a]->query(1,n,b,n);
return h;
}
int can(int M, int K[]) {
sort(K,K+M);
int cnt=0;
used=used->clear(1, n);
for (int i=0; i<M; i++) {
cnt=assign(root[K[i]], used, 1, n, K[i], n, K[i]);
if(cnt<K[i]) return 0;
assert(cnt==K[i]);
}
return 1;
}
static inline int _readInt() {
int x;scanf("%d",&x);
return x;
}
int main() {
int N;
N = _readInt();
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) {
A[i] = _readInt();
B[i] = _readInt();
}
init(N, A, B);
int Q;
Q = _readInt();
for (int i = 0; i < Q; ++i) {
int M;
M = _readInt();
int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
for (int j = 0; j < M; ++j) {
K[j] = _readInt();
}
printf("%d\n", can(M, K));
}
return 0;
}