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;
}
Compilation message (stderr)
teams.cpp: In function 'int assign(node*, node2*&, int, int, int, int, int)':
teams.cpp:97:75: warning: declaration of 'used' shadows a global declaration [-Wshadow]
int assign(node* rt, node2* &used, int start, int end, int a, int b, int v) {
^
teams.cpp:95:8: note: shadowed declaration is here
node2* used;
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |