# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
780603 |
2023-07-12T10:45:55 Z |
dozer |
Teams (IOI15_teams) |
C++14 |
|
2724 ms |
524288 KB |
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define sp " "
#define pii pair<int, int>
#define LOGN 20
const int S = 400;
int tree[S + 5][100005];
int a[500005], b[500005], n;
void update(int bit[], int x, int val){
while(x <= n){
bit[x] += val;
int lsb = x & -x;
x += lsb;
}
}
int query(int bit[], int x){
int ans = 0;
while(x > 0){
ans += bit[x];
int lsb = x & -x;
x -= lsb;
}
return ans;
}
void init(int N, int A[], int B[]) {
n = N;
vector<int> v(N);
iota(v.begin(), v.end(), 0);
sort(v.begin(), v.end(), [&](int a, int b){
if (B[a] == B[b]) return A[a] < A[b];
return B[a] < B[b];
});
for (int i = 0; i < N; i++)
{
a[i] = A[v[i]], b[i] = B[v[i]];
}
for (int i = 0; i < N; i++){
int g = i / S;
update(tree[g], a[i], 1);
}
}
int can(int M, int K[]) {
sort(K, K + M);
vector<int> vis(n, 0);
vector<array<int, 3>> queries;
int ans = 1;
for (int i = 0; i < M; i++){
int pos = 0;
for (int j = LOGN; j >= 0; j--){
int tmp = pos + (1<<j);
if (tmp < n && b[tmp] < K[i]) pos = tmp;
}
if (b[pos] < K[i]) pos++;
int curr = K[i];
while(pos < n && curr > 0){
if (a[pos] > K[i]){
update(tree[pos / S], a[pos], -1);
queries.pb({pos / S, a[pos], 1});
pos++;
continue;
}
int x = query(tree[pos / S], K[i]);
if (x > 0){
curr--;
update(tree[pos / S], 1, -1);
queries.pb({pos / S, 1, 1});
}
pos++;
}
/*
while(pos < n && curr > 0){
int rem = query(tree[pos / S], K[i]);
int diff = min(rem, curr);
curr -= diff;
update(tree[pos / S], 1, -diff);
queries.pb({pos / S, 1, diff});
pos += S;
}*/
if (curr > 0) ans = 0;
}
for (auto i : queries){
update(tree[i[0]], i[1], i[2]);
}
return ans;
}
Compilation message
teams.cpp: In lambda function:
teams.cpp:37:42: warning: declaration of 'b' shadows a global declaration [-Wshadow]
37 | sort(v.begin(), v.end(), [&](int a, int b){
| ~~~~^
teams.cpp:13:16: note: shadowed declaration is here
13 | int a[500005], b[500005], n;
| ^
teams.cpp:37:35: warning: declaration of 'a' shadows a global declaration [-Wshadow]
37 | sort(v.begin(), v.end(), [&](int a, int b){
| ~~~~^
teams.cpp:13:5: note: shadowed declaration is here
13 | int a[500005], b[500005], n;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
17 ms |
12736 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2716 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2724 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
270 ms |
328660 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |