# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
287410 |
2020-08-31T16:45:24 Z |
shayan_p |
Teams (IOI15_teams) |
C++17 |
|
3844 ms |
507228 KB |
// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "teams.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10, SQ = 1000;
pii p[maxn];
int n;
vector<pii> vec[4 * maxn];
vector<int> vecId[4 * maxn];
vector<int> LC[4 * maxn], RC[4 * maxn];
bool leaf[4 * maxn];
int used[4 * maxn];
int lazyUsed[4 * maxn];
void shift(int l, int r, int id){
if(leaf[id] == 0)
return;
assert(r-l > 1);
leaf[id] = 0;
// used[id] = 0;
leaf[2*id] = leaf[2*id+1] = 1;
used[2*id] = LC[id][ used[id] ];
used[2*id + 1] = RC[id][ used[id] ];
lazyUsed[2*id] = used[2*id];
lazyUsed[2*id+1] = used[2*id+1];
}
void build(int l = 0, int r = n, int id = 1){
if(r-l == 1){
vec[id].PB(p[l]);
vecId[id].PB(l);
LC[id].PB(-1), RC[id].PB(-1);
return; // behold LC RC
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id + 1);
int pt1 = 0, pt2 = 0;
while(pt1 < sz(vec[2*id]) || pt2 < sz(vec[2*id+1])){
LC[id].PB(pt1), RC[id].PB(pt2);
if(pt2 == sz(vec[2*id+1]) || (pt1 != sz(vec[2*id]) && vec[2*id][pt1].S > vec[2*id+1][pt2].S))
vec[id].PB(vec[2*id][pt1]), vecId[id].PB(vecId[2*id][pt1]), pt1++;
else
vec[id].PB(vec[2*id+1][pt2]), vecId[id].PB(vecId[2*id+1][pt2]), pt2++;
}
LC[id].PB(pt1), RC[id].PB(pt2);
}
bool bad[maxn];
vector<int> clearBad;
inline void isBad(int x){
if(bad[x])
return;
bad[x] = 1;
clearBad.PB(x);
}
void go(int pos, int &need, int RP = -1, int l = 0, int r = n, int id = 1){
if(id == 1){
int f = -1, s = n;
while(s-f > 1){
int mid = (f + s) >> 1;
if(vec[id][mid].S >= pos)
f = mid;
else
s = mid;
}
if(s - used[id] < need) //////
throw "SHIT";
RP = s;
}
if(need == 0 || RP - used[id] <= 0)
return;
if(p[l].F > pos)
return;
if(p[r-1].F <= pos && leaf[id]){
int delta = min(need, RP - used[id]);
if(delta == RP - used[id]){
need-= delta;
used[id]+= delta;
lazyUsed[id] = used[id];
return;
}
}
if(r-l < SQ){
for(int i = 0; i < lazyUsed[id]; i++)
isBad(vecId[id][i]);
for(int i = r-1; need && i >= l; i--){
if(!bad[i] && p[i].F <= pos && pos <= p[i].S)
isBad(i), --need, used[id]++;
}
return;
}
shift(l, r, id);
int mid = (l+r) >> 1;
go(pos, need, RC[id][RP], mid, r, 2*id+1);
go(pos, need, LC[id][RP], l, mid, 2*id);
}
void init(int n, int l[], int r[]){
for(int i = 0; i < n; i++)
p[i] = {l[i], r[i]};
sort(p, p + n);
::n = n;
build();
}
int can(int m, int a[]){
for(int x : clearBad){
bad[x] = 0;
}
clearBad.clear();
leaf[1] = 1;
used[1] = 0;
lazyUsed[1] = 0;
sort(a, a + m);
int need = 0;
for(int i = m-1; i >= 0; i--){
need+= a[i];
if(need > n)
return 0;
if(i == 0 || a[i] != a[i-1]){
try{
go(a[i], need);
if(need != 0)
throw "SHIT2";
}
catch(...){
return 0;
}
}
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:116:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
116 | void init(int n, int l[], int r[]){
| ^
teams.cpp:20:5: note: shadowed declaration is here
20 | int n;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
128 ms |
188280 KB |
Output is correct |
2 |
Correct |
127 ms |
188412 KB |
Output is correct |
3 |
Correct |
128 ms |
188280 KB |
Output is correct |
4 |
Correct |
125 ms |
188464 KB |
Output is correct |
5 |
Correct |
128 ms |
188280 KB |
Output is correct |
6 |
Correct |
125 ms |
188280 KB |
Output is correct |
7 |
Correct |
125 ms |
188280 KB |
Output is correct |
8 |
Correct |
127 ms |
188280 KB |
Output is correct |
9 |
Correct |
128 ms |
188280 KB |
Output is correct |
10 |
Correct |
126 ms |
188280 KB |
Output is correct |
11 |
Correct |
124 ms |
188280 KB |
Output is correct |
12 |
Correct |
126 ms |
188308 KB |
Output is correct |
13 |
Correct |
126 ms |
188408 KB |
Output is correct |
14 |
Correct |
125 ms |
188280 KB |
Output is correct |
15 |
Correct |
127 ms |
188372 KB |
Output is correct |
16 |
Correct |
127 ms |
188408 KB |
Output is correct |
17 |
Correct |
124 ms |
188280 KB |
Output is correct |
18 |
Correct |
126 ms |
188280 KB |
Output is correct |
19 |
Correct |
133 ms |
188256 KB |
Output is correct |
20 |
Correct |
126 ms |
188408 KB |
Output is correct |
21 |
Correct |
125 ms |
188280 KB |
Output is correct |
22 |
Correct |
124 ms |
188280 KB |
Output is correct |
23 |
Correct |
124 ms |
188280 KB |
Output is correct |
24 |
Correct |
124 ms |
188280 KB |
Output is correct |
25 |
Correct |
125 ms |
188280 KB |
Output is correct |
26 |
Correct |
126 ms |
188248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
426 ms |
250604 KB |
Output is correct |
2 |
Correct |
420 ms |
250604 KB |
Output is correct |
3 |
Correct |
429 ms |
250732 KB |
Output is correct |
4 |
Correct |
432 ms |
251112 KB |
Output is correct |
5 |
Correct |
409 ms |
250984 KB |
Output is correct |
6 |
Correct |
409 ms |
250732 KB |
Output is correct |
7 |
Correct |
412 ms |
250988 KB |
Output is correct |
8 |
Correct |
413 ms |
251244 KB |
Output is correct |
9 |
Correct |
399 ms |
250476 KB |
Output is correct |
10 |
Correct |
408 ms |
250604 KB |
Output is correct |
11 |
Correct |
403 ms |
250604 KB |
Output is correct |
12 |
Correct |
409 ms |
250680 KB |
Output is correct |
13 |
Correct |
416 ms |
250604 KB |
Output is correct |
14 |
Correct |
419 ms |
250604 KB |
Output is correct |
15 |
Correct |
422 ms |
250604 KB |
Output is correct |
16 |
Correct |
417 ms |
250604 KB |
Output is correct |
17 |
Correct |
411 ms |
250732 KB |
Output is correct |
18 |
Correct |
403 ms |
250604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
442 ms |
250732 KB |
Output is correct |
2 |
Correct |
437 ms |
250536 KB |
Output is correct |
3 |
Correct |
1026 ms |
253292 KB |
Output is correct |
4 |
Correct |
432 ms |
250988 KB |
Output is correct |
5 |
Correct |
697 ms |
251116 KB |
Output is correct |
6 |
Correct |
573 ms |
251116 KB |
Output is correct |
7 |
Correct |
698 ms |
251116 KB |
Output is correct |
8 |
Correct |
586 ms |
251116 KB |
Output is correct |
9 |
Correct |
402 ms |
250772 KB |
Output is correct |
10 |
Correct |
407 ms |
250604 KB |
Output is correct |
11 |
Correct |
431 ms |
250732 KB |
Output is correct |
12 |
Correct |
808 ms |
250768 KB |
Output is correct |
13 |
Correct |
1006 ms |
250840 KB |
Output is correct |
14 |
Correct |
1229 ms |
251584 KB |
Output is correct |
15 |
Correct |
658 ms |
250600 KB |
Output is correct |
16 |
Correct |
617 ms |
250732 KB |
Output is correct |
17 |
Correct |
588 ms |
250860 KB |
Output is correct |
18 |
Correct |
528 ms |
250656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1667 ms |
499340 KB |
Output is correct |
2 |
Correct |
1657 ms |
499172 KB |
Output is correct |
3 |
Correct |
3373 ms |
502236 KB |
Output is correct |
4 |
Correct |
1628 ms |
499292 KB |
Output is correct |
5 |
Correct |
3025 ms |
501724 KB |
Output is correct |
6 |
Correct |
2369 ms |
501852 KB |
Output is correct |
7 |
Correct |
2984 ms |
501728 KB |
Output is correct |
8 |
Correct |
2448 ms |
501724 KB |
Output is correct |
9 |
Correct |
1502 ms |
499172 KB |
Output is correct |
10 |
Correct |
1496 ms |
499684 KB |
Output is correct |
11 |
Correct |
2264 ms |
499812 KB |
Output is correct |
12 |
Correct |
3774 ms |
499936 KB |
Output is correct |
13 |
Correct |
3595 ms |
505896 KB |
Output is correct |
14 |
Correct |
3844 ms |
507228 KB |
Output is correct |
15 |
Correct |
2154 ms |
506404 KB |
Output is correct |
16 |
Correct |
2209 ms |
506588 KB |
Output is correct |
17 |
Correct |
2008 ms |
505984 KB |
Output is correct |
18 |
Correct |
1928 ms |
505948 KB |
Output is correct |