#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
const int N = 5e5 + 5, K = 800, INF = 1e9 + 5;
int B_SIZE, B_CNT;
int n, blockmin[N], blockmax[N];
pair<int, int> arr[N];
vector<pair<int, int>> block[N];
struct Fenwick{
int tree[K], preup = -1;
vector<pair<int, int>> hist;
int getsum(int r){
int sum = 0;
for(int i = r + 1; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
int query(int pos){
return getsum(pos) - getsum(pos - 1);
}
void update(int pos, int val, bool keephist = true){
if(keephist) hist.push_back({pos, val});
for(int i = pos + 1; i < K; i += i & -i) tree[i] += val;
}
void clearhist(){
for(int i = (int)hist.size() - 1; i >= 0; i--) update(hist[i].first, -hist[i].second, false);
hist.clear();
preup = -1;
}
};
Fenwick fw[K];
void init(int N_, int A[], int B[]){
n = N_;
B_SIZE = (int)sqrt(n) + 1, B_CNT = (n + B_SIZE - 1) / B_SIZE;
for(int i = 0; i < n; i++) arr[i] = {A[i], B[i]};
sort(arr, arr + n);
for(int i = 0; i < n; i++) block[i / B_SIZE].push_back({arr[i].second, arr[i].first});
for(int i = 0; i < B_CNT; i++){
blockmin[i] = INF, blockmax[i] = -INF;
sort(block[i].begin(), block[i].end(), greater<pair<int, int>>());
for(int j = 0; j < block[i].size(); j++){
blockmin[i] = min(blockmin[i], block[i][j].second);
blockmax[i] = max(blockmax[i], block[i][j].second);
fw[i].update(j, 1, false);
}
}
}
int can(int M, int k[]){
sort(k, k + M, greater<int>());
for(int i = 0; i < B_CNT; i++) fw[i].clearhist();
for(int cur = 0; cur < M; cur++){
int rem = k[cur], ptr = B_CNT - 1;
while(rem > 0){
if(ptr == -1) return 0;
else if(blockmin[ptr] <= k[cur]){
if(blockmax[ptr] <= k[cur]){
int l = -1, r = block[ptr].size(), m;
while(r - l > 1){
m = l + (r - l) / 2;
if(block[ptr][m].first >= k[cur]) l = m;
else r = m;
}
int cnt = max(fw[ptr].getsum(l), 0);
if(cnt < rem){
rem -= cnt;
fw[ptr].preup = max(fw[ptr].preup, l);
fw[ptr].update(0, -cnt);
ptr--;
continue;
}
}
vector<pair<int, int>> v;
for(int j = 0; j < block[ptr].size(); j++){
if(block[ptr][j].first >= k[cur] && block[ptr][j].second <= k[cur] && fw[ptr].query(j) > 0 && j > fw[ptr].preup){
v.push_back({block[ptr][j].second, j});
}
}
sort(v.begin(), v.end(), greater<pair<int, int>>());
for(int i = 0; i < v.size(); i++){
if(rem == 0) break;
fw[ptr].update(v[i].second, -1);
rem--;
}
}
ptr--;
}
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j = 0; j < block[i].size(); j++){
| ~~^~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:81:52: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
81 | int l = -1, r = block[ptr].size(), m;
| ~~~~~~~~~~~~~~~^~
teams.cpp:106:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int j = 0; j < block[ptr].size(); j++){
| ~~^~~~~~~~~~~~~~~~~~~
teams.cpp:114:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14548 KB |
Output is correct |
2 |
Correct |
8 ms |
14548 KB |
Output is correct |
3 |
Correct |
8 ms |
14552 KB |
Output is correct |
4 |
Correct |
8 ms |
14600 KB |
Output is correct |
5 |
Correct |
9 ms |
14548 KB |
Output is correct |
6 |
Correct |
10 ms |
14548 KB |
Output is correct |
7 |
Correct |
10 ms |
14560 KB |
Output is correct |
8 |
Correct |
8 ms |
14548 KB |
Output is correct |
9 |
Correct |
8 ms |
14548 KB |
Output is correct |
10 |
Correct |
7 ms |
14548 KB |
Output is correct |
11 |
Correct |
9 ms |
14612 KB |
Output is correct |
12 |
Correct |
8 ms |
14548 KB |
Output is correct |
13 |
Correct |
8 ms |
14548 KB |
Output is correct |
14 |
Correct |
8 ms |
14592 KB |
Output is correct |
15 |
Correct |
8 ms |
14616 KB |
Output is correct |
16 |
Correct |
8 ms |
14584 KB |
Output is correct |
17 |
Correct |
8 ms |
14548 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14548 KB |
Output is correct |
20 |
Correct |
9 ms |
14548 KB |
Output is correct |
21 |
Correct |
9 ms |
14552 KB |
Output is correct |
22 |
Correct |
9 ms |
14584 KB |
Output is correct |
23 |
Correct |
8 ms |
14548 KB |
Output is correct |
24 |
Correct |
7 ms |
14584 KB |
Output is correct |
25 |
Correct |
7 ms |
14588 KB |
Output is correct |
26 |
Correct |
9 ms |
14504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
17364 KB |
Output is correct |
2 |
Correct |
26 ms |
17436 KB |
Output is correct |
3 |
Correct |
27 ms |
17440 KB |
Output is correct |
4 |
Correct |
29 ms |
17784 KB |
Output is correct |
5 |
Correct |
25 ms |
18592 KB |
Output is correct |
6 |
Correct |
24 ms |
17356 KB |
Output is correct |
7 |
Correct |
25 ms |
18596 KB |
Output is correct |
8 |
Correct |
26 ms |
18516 KB |
Output is correct |
9 |
Correct |
863 ms |
63276 KB |
Output is correct |
10 |
Correct |
606 ms |
51008 KB |
Output is correct |
11 |
Correct |
99 ms |
22760 KB |
Output is correct |
12 |
Correct |
26 ms |
18216 KB |
Output is correct |
13 |
Correct |
25 ms |
17448 KB |
Output is correct |
14 |
Correct |
23 ms |
17436 KB |
Output is correct |
15 |
Correct |
32 ms |
17428 KB |
Output is correct |
16 |
Correct |
26 ms |
17436 KB |
Output is correct |
17 |
Correct |
22 ms |
17492 KB |
Output is correct |
18 |
Correct |
24 ms |
17492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
17768 KB |
Output is correct |
2 |
Correct |
48 ms |
17744 KB |
Output is correct |
3 |
Execution timed out |
4067 ms |
20940 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
154 ms |
28836 KB |
Output is correct |
2 |
Correct |
166 ms |
28868 KB |
Output is correct |
3 |
Execution timed out |
4065 ms |
34472 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |