# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
17284 |
2015-11-11T18:15:59 Z |
erdemkiraz |
Teams (IOI15_teams) |
C++ |
|
988 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
#include "teams.h"
const int N = 5e5 + 5;
ii a[N];
class node{ public:
int x;
node *l, *r, *lazy;
node() {
x = 0;
l = r = lazy = 0;
}
};
typedef node* pNode;
pNode del;
pNode t[N];
pNode insert(pNode x, int l, int r, int x1) {
pNode nw = new node;
if(l == r) {
nw -> x = 1;
return nw;
}
int m = l + r >> 1;
if(x1 <= m) {
nw -> l = insert(x -> l, l, m, x1);
nw -> r = x -> r;
}
else {
nw -> l = x -> l;
nw -> r = insert(x -> r, m + 1, r, x1);
}
nw -> x = nw -> l -> x + nw -> r -> x;
return nw;
}
int n;
void init(pNode x, int l, int r) {
if(l == r)
return;
int m = l + r >> 1;
x -> l = new node;
x -> r = new node;
init(x -> l, l, m);
init(x -> r, m + 1, r);
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 1; i <= n; i++) {
a[i] = ii(B[i - 1], A[i - 1]);
}
sort(a + 1, a + n + 1);
vector < ii > vs;
for(int i = 1; i <= n; i++)
vs.push_back(ii(a[i].second, i));
sort(vs.begin(), vs.end());
int ptr = 0;
t[0] = new node;
init(t[0], 1, n);
for(int i = 1; i <= n; i++) {
t[i] = t[i - 1];
//printf("vs = %d ", i);
while(ptr < vs.size() and vs[ptr].first <= i) {
//printf("%d ", vs[ptr].second);
t[i] = insert(t[i], 1, n, vs[ptr].second);
ptr++;
}
//puts("");
}
del = new node;
init(del, 1, n);
}
void push(pNode x, pNode del) {
if(del -> lazy) {
del -> l -> x = del -> lazy -> l -> x;
del -> r -> x = del -> lazy -> r -> x;
del -> l -> lazy = del -> lazy -> l;
del -> r -> lazy = del -> lazy -> r;
del -> lazy = 0;
}
}
int get(pNode x, pNode del, int l, int r, int x1, int x2, int k) {
if(x1 <= l and r <= x2 and x -> x - del -> x <= k) {
del -> lazy = x;
int ret = x -> x - del -> x;
del -> x += ret;
return ret;
}
if(x2 < l or r < x1 or l == r or del -> x == x -> x)
return 0;
int m = l + r >> 1;
push(x, del);
int lf = get(x -> l, del -> l, l, m, x1, x2, k);
if(lf == k) {
del -> x = del -> l -> x + del -> r -> x;
return k;
}
k -= lf;
int rf = get(x -> r, del -> r, m + 1, r, x1, x2, k);
del -> x = del -> l -> x + del -> r -> x;
return lf + rf;
}
void clear(pNode x) {
if(x -> x and x -> l)
clear(x -> l);
if(x -> x and x -> r)
clear(x -> r);
x -> lazy = 0;
x -> x = 0;
}
int can(int M, int K[]) {
sort(K, K + M);
int sum = 0;
for(int i = 0; i < M; i++) {
if(sum + K[i] > n)
return 0;
sum += K[i];
}
clear(del);
for(int i = 0; i < M; i++) {
int id = lower_bound(a + 1, a + n + 1, ii(K[i], 0)) - a;
//printf("id = %d ", id);
int res = get(t[K[i]], del, 1, n, id, n, K[i]);
//printf("res = %d\n", res);
if(res != K[i])
return 0;
}
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
9544 KB |
Output is correct |
2 |
Correct |
0 ms |
9544 KB |
Output is correct |
3 |
Correct |
2 ms |
9544 KB |
Output is correct |
4 |
Correct |
0 ms |
9544 KB |
Output is correct |
5 |
Correct |
0 ms |
9544 KB |
Output is correct |
6 |
Correct |
0 ms |
9544 KB |
Output is correct |
7 |
Correct |
0 ms |
9544 KB |
Output is correct |
8 |
Correct |
0 ms |
9544 KB |
Output is correct |
9 |
Correct |
2 ms |
9544 KB |
Output is correct |
10 |
Correct |
0 ms |
9544 KB |
Output is correct |
11 |
Correct |
0 ms |
9544 KB |
Output is correct |
12 |
Correct |
0 ms |
9544 KB |
Output is correct |
13 |
Correct |
2 ms |
9544 KB |
Output is correct |
14 |
Correct |
2 ms |
9544 KB |
Output is correct |
15 |
Correct |
2 ms |
9544 KB |
Output is correct |
16 |
Correct |
0 ms |
9544 KB |
Output is correct |
17 |
Correct |
0 ms |
9544 KB |
Output is correct |
18 |
Correct |
0 ms |
9544 KB |
Output is correct |
19 |
Correct |
0 ms |
9544 KB |
Output is correct |
20 |
Correct |
2 ms |
9544 KB |
Output is correct |
21 |
Correct |
0 ms |
9544 KB |
Output is correct |
22 |
Correct |
2 ms |
9544 KB |
Output is correct |
23 |
Correct |
0 ms |
9544 KB |
Output is correct |
24 |
Correct |
0 ms |
9544 KB |
Output is correct |
25 |
Correct |
0 ms |
9544 KB |
Output is correct |
26 |
Correct |
0 ms |
9544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
112992 KB |
Output is correct |
2 |
Correct |
162 ms |
112992 KB |
Output is correct |
3 |
Correct |
172 ms |
112992 KB |
Output is correct |
4 |
Correct |
153 ms |
112992 KB |
Output is correct |
5 |
Correct |
118 ms |
112992 KB |
Output is correct |
6 |
Correct |
71 ms |
112992 KB |
Output is correct |
7 |
Correct |
89 ms |
112992 KB |
Output is correct |
8 |
Correct |
117 ms |
112992 KB |
Output is correct |
9 |
Correct |
130 ms |
112992 KB |
Output is correct |
10 |
Correct |
129 ms |
112992 KB |
Output is correct |
11 |
Correct |
86 ms |
112992 KB |
Output is correct |
12 |
Correct |
128 ms |
112992 KB |
Output is correct |
13 |
Correct |
86 ms |
112992 KB |
Output is correct |
14 |
Correct |
144 ms |
112992 KB |
Output is correct |
15 |
Correct |
159 ms |
112992 KB |
Output is correct |
16 |
Correct |
143 ms |
112992 KB |
Output is correct |
17 |
Correct |
110 ms |
112992 KB |
Output is correct |
18 |
Correct |
104 ms |
112992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
112992 KB |
Output is correct |
2 |
Correct |
185 ms |
112992 KB |
Output is correct |
3 |
Correct |
424 ms |
115004 KB |
Output is correct |
4 |
Correct |
167 ms |
112992 KB |
Output is correct |
5 |
Correct |
241 ms |
112992 KB |
Output is correct |
6 |
Correct |
223 ms |
112992 KB |
Output is correct |
7 |
Correct |
136 ms |
112992 KB |
Output is correct |
8 |
Correct |
211 ms |
112992 KB |
Output is correct |
9 |
Correct |
150 ms |
112992 KB |
Output is correct |
10 |
Correct |
180 ms |
112992 KB |
Output is correct |
11 |
Correct |
191 ms |
112992 KB |
Output is correct |
12 |
Correct |
250 ms |
112992 KB |
Output is correct |
13 |
Correct |
329 ms |
112992 KB |
Output is correct |
14 |
Correct |
445 ms |
113816 KB |
Output is correct |
15 |
Correct |
198 ms |
112992 KB |
Output is correct |
16 |
Correct |
227 ms |
112992 KB |
Output is correct |
17 |
Correct |
176 ms |
112992 KB |
Output is correct |
18 |
Correct |
201 ms |
112992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Memory limit exceeded |
988 ms |
524288 KB |
Memory limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |