# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
287347 |
2020-08-31T16:07:20 Z |
Saboon |
Teams (IOI15_teams) |
C++17 |
|
3354 ms |
104148 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
const int SQRT = 2000;
int n;
vector<int> fex[maxn], fen[maxn];
void addinit(int x, int y){
for (; x < maxn; x += x & -x)
fex[x].push_back(y);
}
void add(int x, int y){
for (int idx = x; idx < maxn; idx += idx & -idx){
int idy = lower_bound(fex[idx].begin(),fex[idx].end(),y)-fex[idx].begin()+1;
for (; idy <= fex[idx].size(); idy += idy & -idy)
fen[idx][idy] ++;
}
}
int get(int x, int y){
int ret = 0;
for (; x; x -= x & -x){
int idy = upper_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin();
for (;idy; idy -= idy & -idy)
ret += fen[x][idy];
}
return ret;
}
int get(int x, int l, int r){
return get(x, r) - get(x, l-1);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 0; i < n; i++)
addinit(A[i],B[i]);
for (int i = 1; i < maxn; i++){
sort(fex[i].begin(), fex[i].end());
fex[i].resize(unique(fex[i].begin(),fex[i].end())-fex[i].begin());
fen[i].resize(fex[i].size()+1);
}
for (int i = 0; i < n; i++)
add(A[i],B[i]);
}
int up[SQRT], bup[SQRT];
int Uses[SQRT];
int can(int m, int k[]){
sort(k,k+m);
long long sum = 0;
for (int i = 0; i < m; i++)
sum += k[i];
if (sum > n)
return 0;
int idx = 0, cnt = 0;
for (int i = 0; i < m; i++){
cnt ++;
if (i == m-1 or k[i] != k[i+1]){
up[idx] = k[i], bup[idx] = cnt*k[i];
cnt = 0, idx++;
}
}
int CommonUse = 0;
up[idx] = n+1;
for (int i = 0; i < idx; i++){
Uses[i] = 0;
int Marked = 0;
for (int j = 0; j < i; j++){
if (Uses[j] == 0)
continue;
int t = get(up[j], up[i], up[i+1]-1) - Marked;
int tmp = min(t, Uses[j]);
Marked += tmp, Uses[j] -= tmp, CommonUse -= tmp;
}
int me = get(up[i], up[i], up[i+1]-1) - Marked;
bup[i] = max(0, bup[i]-me);
int T = get(up[i], up[i+1], n) - CommonUse;
if (T < bup[i])
return 0;
CommonUse += bup[i];
Uses[i] += bup[i];
}
return 1;
}
Compilation message
teams.cpp: In function 'void add(int, int)':
teams.cpp:18:76: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
18 | int idy = lower_bound(fex[idx].begin(),fex[idx].end(),y)-fex[idx].begin()+1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (; idy <= fex[idx].size(); idy += idy & -idy)
| ~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int get(int, int)':
teams.cpp:27:55: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
27 | int idy = upper_bound(fex[x].begin(),fex[x].end(),y)-fex[x].begin();
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
50 ms |
39544 KB |
Output is correct |
2 |
Correct |
50 ms |
39416 KB |
Output is correct |
3 |
Correct |
50 ms |
39416 KB |
Output is correct |
4 |
Correct |
50 ms |
39420 KB |
Output is correct |
5 |
Correct |
50 ms |
39416 KB |
Output is correct |
6 |
Correct |
50 ms |
39544 KB |
Output is correct |
7 |
Correct |
50 ms |
39416 KB |
Output is correct |
8 |
Correct |
51 ms |
39424 KB |
Output is correct |
9 |
Correct |
50 ms |
39416 KB |
Output is correct |
10 |
Correct |
52 ms |
39416 KB |
Output is correct |
11 |
Correct |
50 ms |
39416 KB |
Output is correct |
12 |
Correct |
50 ms |
39544 KB |
Output is correct |
13 |
Correct |
51 ms |
39544 KB |
Output is correct |
14 |
Correct |
50 ms |
39416 KB |
Output is correct |
15 |
Correct |
50 ms |
39416 KB |
Output is correct |
16 |
Correct |
51 ms |
39416 KB |
Output is correct |
17 |
Correct |
50 ms |
39416 KB |
Output is correct |
18 |
Correct |
50 ms |
39416 KB |
Output is correct |
19 |
Correct |
50 ms |
39416 KB |
Output is correct |
20 |
Correct |
50 ms |
39420 KB |
Output is correct |
21 |
Correct |
52 ms |
39524 KB |
Output is correct |
22 |
Correct |
50 ms |
39416 KB |
Output is correct |
23 |
Correct |
51 ms |
39416 KB |
Output is correct |
24 |
Correct |
50 ms |
39416 KB |
Output is correct |
25 |
Correct |
50 ms |
39416 KB |
Output is correct |
26 |
Correct |
50 ms |
39416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
50144 KB |
Output is correct |
2 |
Correct |
390 ms |
50052 KB |
Output is correct |
3 |
Correct |
383 ms |
50140 KB |
Output is correct |
4 |
Correct |
389 ms |
50536 KB |
Output is correct |
5 |
Correct |
190 ms |
46528 KB |
Output is correct |
6 |
Correct |
191 ms |
46400 KB |
Output is correct |
7 |
Correct |
191 ms |
46396 KB |
Output is correct |
8 |
Correct |
194 ms |
46524 KB |
Output is correct |
9 |
Correct |
111 ms |
47800 KB |
Output is correct |
10 |
Correct |
110 ms |
47892 KB |
Output is correct |
11 |
Correct |
117 ms |
47856 KB |
Output is correct |
12 |
Correct |
128 ms |
47940 KB |
Output is correct |
13 |
Correct |
186 ms |
47564 KB |
Output is correct |
14 |
Correct |
301 ms |
49724 KB |
Output is correct |
15 |
Correct |
339 ms |
49628 KB |
Output is correct |
16 |
Correct |
328 ms |
49504 KB |
Output is correct |
17 |
Correct |
129 ms |
46212 KB |
Output is correct |
18 |
Correct |
129 ms |
46040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
50524 KB |
Output is correct |
2 |
Correct |
401 ms |
50524 KB |
Output is correct |
3 |
Correct |
595 ms |
53556 KB |
Output is correct |
4 |
Correct |
400 ms |
50656 KB |
Output is correct |
5 |
Correct |
260 ms |
46780 KB |
Output is correct |
6 |
Correct |
233 ms |
46780 KB |
Output is correct |
7 |
Correct |
208 ms |
46780 KB |
Output is correct |
8 |
Correct |
232 ms |
46780 KB |
Output is correct |
9 |
Correct |
111 ms |
47800 KB |
Output is correct |
10 |
Correct |
107 ms |
48164 KB |
Output is correct |
11 |
Correct |
120 ms |
48096 KB |
Output is correct |
12 |
Correct |
999 ms |
48096 KB |
Output is correct |
13 |
Correct |
657 ms |
47936 KB |
Output is correct |
14 |
Correct |
650 ms |
52308 KB |
Output is correct |
15 |
Correct |
365 ms |
49884 KB |
Output is correct |
16 |
Correct |
359 ms |
50012 KB |
Output is correct |
17 |
Correct |
145 ms |
46300 KB |
Output is correct |
18 |
Correct |
160 ms |
46440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2340 ms |
90880 KB |
Output is correct |
2 |
Correct |
2292 ms |
90848 KB |
Output is correct |
3 |
Correct |
3103 ms |
96752 KB |
Output is correct |
4 |
Correct |
2297 ms |
90936 KB |
Output is correct |
5 |
Correct |
947 ms |
73060 KB |
Output is correct |
6 |
Correct |
907 ms |
74104 KB |
Output is correct |
7 |
Correct |
809 ms |
74128 KB |
Output is correct |
8 |
Correct |
898 ms |
74088 KB |
Output is correct |
9 |
Correct |
370 ms |
82256 KB |
Output is correct |
10 |
Correct |
350 ms |
81908 KB |
Output is correct |
11 |
Correct |
1064 ms |
82392 KB |
Output is correct |
12 |
Correct |
3354 ms |
81612 KB |
Output is correct |
13 |
Correct |
2422 ms |
79792 KB |
Output is correct |
14 |
Correct |
3334 ms |
104148 KB |
Output is correct |
15 |
Correct |
1628 ms |
91508 KB |
Output is correct |
16 |
Correct |
1593 ms |
91580 KB |
Output is correct |
17 |
Correct |
417 ms |
77132 KB |
Output is correct |
18 |
Correct |
420 ms |
77384 KB |
Output is correct |