# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
22022 |
2017-04-28T21:21:42 Z |
sbansalcs |
Teams (IOI15_teams) |
C++14 |
|
936 ms |
411664 KB |
#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
teams.cpp: In function 'int assign(node*, node2*&, int, int, int, int, int)':
teams.cpp:96: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:94:8: note: shadowed declaration is here
node2* used;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
13780 KB |
Output is correct |
2 |
Correct |
0 ms |
13780 KB |
Output is correct |
3 |
Correct |
0 ms |
13780 KB |
Output is correct |
4 |
Correct |
0 ms |
13780 KB |
Output is correct |
5 |
Runtime error |
0 ms |
13780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
86552 KB |
Output is correct |
2 |
Correct |
129 ms |
86552 KB |
Output is correct |
3 |
Correct |
136 ms |
86552 KB |
Output is correct |
4 |
Correct |
136 ms |
86552 KB |
Output is correct |
5 |
Correct |
106 ms |
86552 KB |
Output is correct |
6 |
Correct |
83 ms |
86552 KB |
Output is correct |
7 |
Runtime error |
66 ms |
86552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
86552 KB |
Output is correct |
2 |
Correct |
153 ms |
86552 KB |
Output is correct |
3 |
Runtime error |
139 ms |
86552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
936 ms |
411664 KB |
Output is correct |
2 |
Correct |
929 ms |
411664 KB |
Output is correct |
3 |
Runtime error |
916 ms |
411664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |