| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 22025 |
2017-04-28T21:49:16 Z |
sbansalcs |
Teams (IOI15_teams) |
C++14 |
|
4000 ms |
388228 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;
void err() {
while (1) {
}
}
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()
// }
};
node* points[N*4];
int val[N*4];
void build(int idx, int start, int end) {
points[idx]=NULL;
val[idx]=0;
if(start!=end) {
build(idx*2, start, mid);
build(idx*2+1, mid+1, end);
}
}
void clear(int idx, int start, int end) {
if(val[idx]!=0 || points[idx]!=NULL) {
if(start!=end) clear(idx*2,start,mid),clear(idx*2+1,mid+1,end);
}
val[idx]=0;
points[idx]=NULL;
}
void lz(int idx,int start, int end) {
if(points[idx]==NULL) return;
val[idx]=points[idx]->val;
if(start!=end) {
points[idx*2]=points[idx]->l;
points[idx*2+1]=points[idx]->r;
}
points[idx]=NULL;
}
//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, int idx, int start, int end, int a, int b, int v) {
if(rt==NULL) err();
// if(used==NULL) err();
// used=used->lz(start,end);
lz(idx, start, end);
if(start>b || end<a) return 0;
if(v==0) return 0;
int av =rt->val-val[idx];
if(start>=a && end<=b) {
if(av<=v) {
// used->points=rt;
points[idx]=rt;
lz(idx, start, end);
return av;
}
else {
int lf=assign(rt->l, idx*2, start, mid, a, b, v);
int rf=assign(rt->r, idx*2+1, mid+1, end, a, b, v-lf);
return rf+lf;
}
}
else {
int lf=assign(rt->l, idx*2, start, mid, a, b, v);
int rf=assign(rt->r, idx*2+1, 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);
build(1, 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);
clear(1, 1, n);
for (int i=0; i<M; i++) {
cnt=assign(root[K[i]], 1, 1, n, K[i], n, K[i]);
if(cnt<K[i]) return 0;
// assert(cnt==K[i]);
}
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
37204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
37204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
37204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
37204 KB |
Output is correct |
| 5 |
Execution timed out |
4000 ms |
37204 KB |
Execution timed out |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
100604 KB |
Output is correct |
| 2 |
Correct |
129 ms |
100604 KB |
Output is correct |
| 3 |
Correct |
149 ms |
100604 KB |
Output is correct |
| 4 |
Correct |
163 ms |
100604 KB |
Output is correct |
| 5 |
Correct |
73 ms |
100604 KB |
Output is correct |
| 6 |
Correct |
59 ms |
100604 KB |
Output is correct |
| 7 |
Execution timed out |
4000 ms |
100604 KB |
Execution timed out |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
100604 KB |
Output is correct |
| 2 |
Correct |
129 ms |
100604 KB |
Output is correct |
| 3 |
Execution timed out |
4000 ms |
100604 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
893 ms |
388228 KB |
Output is correct |
| 2 |
Correct |
919 ms |
388228 KB |
Output is correct |
| 3 |
Execution timed out |
4000 ms |
388228 KB |
Execution timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
