# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
623505 |
2022-08-05T17:28:48 Z |
BalintR |
Teams (IOI15_teams) |
C++17 |
|
1544 ms |
126820 KB |
#include <bits/stdc++.h>
using namespace std;
#include "teams.h"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pb push_back
#define fs first
#define sn second
const int MN = 5e5 + 5, TREE_SZ = 1 << 20;
int n, q;
pii arr[MN];
int mem[10 << 20], tree[TREE_SZ], vecSz[TREE_SZ], sumDec[TREE_SZ], lastRem[TREE_SZ];
vi needReset;
int t, l, v;
const int r = TREE_SZ >> 1;
void update(int i, int segL, int segR, int prvLast){
if(r <= segL || l >= segR || v == 0) return;
needReset.pb(i);
if(prvLast > lastRem[i]) sumDec[i] = 0;
lastRem[i] = prvLast = max(lastRem[i], prvLast);
if(l <= segL){
int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i];
if(gv <= v){
sumDec[i] = 0;
lastRem[i] = t;
v -= gv;
return;
}
}
if(segL + 1 == segR){
sumDec[i] += v;
v = 0;
return;
}
int mid = (segL + segR) >> 1;
int oldV = v;
update(i * 2, segL, mid, prvLast);
sumDec[i] += oldV - v;
if(v == 0) return;
oldV = v;
update(i * 2 + 1, mid, segR, prvLast);
sumDec[i] += oldV - v;
}
void init(int N, int *A, int *B){
n = N;
for (int i = 0; i < n; ++i) {
arr[i] = {A[i], B[i]};
for(int j = r + B[i]; j; j >>= 1) vecSz[j]++;
}
sort(arr, arr + n);
for (int i = 1; i < TREE_SZ; ++i) {
tree[i] = tree[i-1] + vecSz[i-1];
vecSz[i-1] = 0;
}
for (int i = 0; i < n; ++i) {
for(int j = r + arr[i].sn; j; j >>= 1){
mem[tree[j] + vecSz[j]++] = arr[i].fs;
}
}
}
int can(int k, int *reqSizes){
ll sum = 0;
for (int i = 0; i < k; ++i) sum += reqSizes[i];
if(sum > n) return 0;
sort(reqSizes, reqSizes + k);
bool works = true;
for (int i = 0; i < k; ++i) {
t = l = v = reqSizes[i];
update(1, 0, r, 0);
if(v){
works = false;
break;
}
}
for(int ind : needReset) sumDec[ind] = lastRem[ind] = 0;
needReset.clear();
return works;
}
Compilation message
teams.cpp: In function 'void update(int, int, int, int)':
teams.cpp:27:140: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
27 | int gv = upper_bound(mem + tree[i],mem + tree[i] + vecSz[i], t) - upper_bound(mem + tree[i], mem + tree[i] + vecSz[i], lastRem[i]) - sumDec[i];
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
8532 KB |
Output is correct |
2 |
Correct |
10 ms |
8628 KB |
Output is correct |
3 |
Correct |
13 ms |
8532 KB |
Output is correct |
4 |
Correct |
10 ms |
8532 KB |
Output is correct |
5 |
Correct |
10 ms |
8640 KB |
Output is correct |
6 |
Correct |
10 ms |
8496 KB |
Output is correct |
7 |
Correct |
11 ms |
8636 KB |
Output is correct |
8 |
Correct |
10 ms |
8532 KB |
Output is correct |
9 |
Correct |
10 ms |
8532 KB |
Output is correct |
10 |
Correct |
11 ms |
8732 KB |
Output is correct |
11 |
Correct |
13 ms |
8632 KB |
Output is correct |
12 |
Correct |
13 ms |
8660 KB |
Output is correct |
13 |
Correct |
14 ms |
8640 KB |
Output is correct |
14 |
Correct |
11 ms |
8532 KB |
Output is correct |
15 |
Correct |
11 ms |
8556 KB |
Output is correct |
16 |
Correct |
10 ms |
8532 KB |
Output is correct |
17 |
Correct |
11 ms |
8616 KB |
Output is correct |
18 |
Correct |
11 ms |
8532 KB |
Output is correct |
19 |
Correct |
11 ms |
8584 KB |
Output is correct |
20 |
Correct |
12 ms |
8532 KB |
Output is correct |
21 |
Correct |
12 ms |
8544 KB |
Output is correct |
22 |
Correct |
11 ms |
8624 KB |
Output is correct |
23 |
Correct |
11 ms |
8636 KB |
Output is correct |
24 |
Correct |
11 ms |
8584 KB |
Output is correct |
25 |
Correct |
10 ms |
8548 KB |
Output is correct |
26 |
Correct |
10 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
19160 KB |
Output is correct |
2 |
Correct |
45 ms |
19100 KB |
Output is correct |
3 |
Correct |
40 ms |
19084 KB |
Output is correct |
4 |
Correct |
42 ms |
19668 KB |
Output is correct |
5 |
Correct |
34 ms |
18812 KB |
Output is correct |
6 |
Correct |
33 ms |
18740 KB |
Output is correct |
7 |
Correct |
32 ms |
18788 KB |
Output is correct |
8 |
Correct |
33 ms |
18688 KB |
Output is correct |
9 |
Correct |
93 ms |
27316 KB |
Output is correct |
10 |
Correct |
47 ms |
20748 KB |
Output is correct |
11 |
Correct |
32 ms |
18892 KB |
Output is correct |
12 |
Correct |
28 ms |
18752 KB |
Output is correct |
13 |
Correct |
36 ms |
19088 KB |
Output is correct |
14 |
Correct |
33 ms |
18900 KB |
Output is correct |
15 |
Correct |
37 ms |
19132 KB |
Output is correct |
16 |
Correct |
40 ms |
19116 KB |
Output is correct |
17 |
Correct |
35 ms |
19208 KB |
Output is correct |
18 |
Correct |
32 ms |
19220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
19992 KB |
Output is correct |
2 |
Correct |
45 ms |
19840 KB |
Output is correct |
3 |
Correct |
369 ms |
24724 KB |
Output is correct |
4 |
Correct |
40 ms |
19716 KB |
Output is correct |
5 |
Correct |
72 ms |
19608 KB |
Output is correct |
6 |
Correct |
64 ms |
19532 KB |
Output is correct |
7 |
Correct |
39 ms |
19484 KB |
Output is correct |
8 |
Correct |
65 ms |
19500 KB |
Output is correct |
9 |
Correct |
95 ms |
27440 KB |
Output is correct |
10 |
Correct |
91 ms |
20908 KB |
Output is correct |
11 |
Correct |
110 ms |
19524 KB |
Output is correct |
12 |
Correct |
193 ms |
19492 KB |
Output is correct |
13 |
Correct |
314 ms |
20080 KB |
Output is correct |
14 |
Correct |
393 ms |
23324 KB |
Output is correct |
15 |
Correct |
128 ms |
20024 KB |
Output is correct |
16 |
Correct |
103 ms |
20004 KB |
Output is correct |
17 |
Correct |
70 ms |
20052 KB |
Output is correct |
18 |
Correct |
90 ms |
20040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
63760 KB |
Output is correct |
2 |
Correct |
235 ms |
63788 KB |
Output is correct |
3 |
Correct |
1225 ms |
78452 KB |
Output is correct |
4 |
Correct |
235 ms |
63352 KB |
Output is correct |
5 |
Correct |
193 ms |
61092 KB |
Output is correct |
6 |
Correct |
189 ms |
61048 KB |
Output is correct |
7 |
Correct |
126 ms |
61044 KB |
Output is correct |
8 |
Correct |
173 ms |
61152 KB |
Output is correct |
9 |
Correct |
501 ms |
126820 KB |
Output is correct |
10 |
Correct |
276 ms |
62488 KB |
Output is correct |
11 |
Correct |
338 ms |
60244 KB |
Output is correct |
12 |
Correct |
543 ms |
60876 KB |
Output is correct |
13 |
Correct |
1299 ms |
63608 KB |
Output is correct |
14 |
Correct |
1544 ms |
75128 KB |
Output is correct |
15 |
Correct |
334 ms |
63980 KB |
Output is correct |
16 |
Correct |
345 ms |
64032 KB |
Output is correct |
17 |
Correct |
262 ms |
63348 KB |
Output is correct |
18 |
Correct |
256 ms |
63380 KB |
Output is correct |