#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define a first
#define b second
#define pb push_back
#define mp make_pair
#include "teams.h"
int n;
int aa[500001];
int bb[500001];
vector<int> su[500001];
int tree[30*500001];
int l[30*500001];
int r[30*500001];
int root=0;
int dp[500001];
int lab[500001];
int cnt=0;
vector<int> xx[500001];
void build(int no,int ll,int rr){
cnt=max(cnt,no);
if(ll==rr){
tree[no]=0;
}
else{
int mid=(ll+rr)/2;
build(no*2+1,ll,mid);
build(no*2+2,mid+1,rr);
tree[no]=0;
l[no]=no*2+1;
r[no]=no*2+2;
}
}
int update(int no,int ll,int rr,int ind){
if(ll==rr){
cnt++;
tree[cnt]=tree[no]+1;
return cnt;
}
else{
int mid=(ll+rr)/2;
cnt++;
int cur=cnt;
if(ind<=mid){
l[cur]=update(l[no],ll,mid,ind);
r[cur]=r[no];
}
else{
r[cur]=update(r[no],mid+1,rr,ind);
l[cur]=l[no];
}
tree[cur]=tree[l[cur]]+tree[r[cur]];
return cur;
}
}
void init(int nn, int A[], int B[]) {
n=nn;
for(int i=0;i<n;i++){
aa[i]=A[i];
bb[i]=B[i];
su[bb[i]].pb(aa[i]);
xx[aa[i]].pb(bb[i]);
}
build(0,0,n-1);
for(int i=n;i>=1;i--){
for(auto j:su[i]){
root=update(root,0,n-1,j-1);
}
lab[i]=root;
}
}
int query(int no,int ll,int rr,int aa,int bb){
if(rr<aa or ll>bb or aa>bb){
return 0;
}
if(aa<=ll and rr<=bb){
//cout<<ll<<"..."<<rr<<endl;
return tree[no];
}
else{
int mid=(ll+rr)/2;
return query(l[no],ll,mid,aa,bb)+query(r[no],mid+1,rr,aa,bb);
}
}
int can(int m, int k[]){
if(m>300){
int so=0;;
for(int i=0;i<m;i++){
xx[k[i]].pb(n+1);
so+=k[i];
}
if(so>n){
return 0;
}
priority_queue<int> cur;
for(int i=1;i<=n;i++){
for(auto j:xx[i]){
if(j==n+1){
while(cur.size() and -cur.top()<i){
cur.pop();
}
for(int kk=0;kk<i;kk++){
if(cur.size()==0){
for(int ii=0;ii<m;ii++){
xx[k[ii]].pop_back();
}
return 0;
}
cur.pop();
}
}
else{
cur.push(-j);
}
}
}
for(int i=0;i<m;i++){
xx[k[i]].pop_back();
}
return 1;
}
sort(k,k+m);
for(int i=0;i<m;i++){
dp[i]=query(lab[k[i]],0,n-1,0,k[i]-1)-k[i];
for(int j=0;j<i;j++){
dp[i]=min(dp[i],dp[j]+query(lab[k[i]],0,n-1,k[j],k[i]-1)-k[i]);
}
if(dp[i]<0){
return 0;
}
}
return 1;
}
Compilation message
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:79:45: warning: declaration of 'bb' shadows a global declaration [-Wshadow]
79 | int query(int no,int ll,int rr,int aa,int bb){
| ^
teams.cpp:12:5: note: shadowed declaration is here
12 | int bb[500001];
| ^~
teams.cpp:79:45: warning: declaration of 'aa' shadows a global declaration [-Wshadow]
79 | int query(int no,int ll,int rr,int aa,int bb){
| ^
teams.cpp:11:5: note: shadowed declaration is here
11 | int aa[500001];
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23808 KB |
Output is correct |
2 |
Correct |
14 ms |
23808 KB |
Output is correct |
3 |
Correct |
15 ms |
23936 KB |
Output is correct |
4 |
Correct |
14 ms |
23808 KB |
Output is correct |
5 |
Correct |
14 ms |
23808 KB |
Output is correct |
6 |
Correct |
15 ms |
24064 KB |
Output is correct |
7 |
Correct |
14 ms |
23936 KB |
Output is correct |
8 |
Correct |
15 ms |
23808 KB |
Output is correct |
9 |
Correct |
14 ms |
23808 KB |
Output is correct |
10 |
Correct |
14 ms |
23808 KB |
Output is correct |
11 |
Correct |
14 ms |
23808 KB |
Output is correct |
12 |
Correct |
17 ms |
23936 KB |
Output is correct |
13 |
Correct |
15 ms |
23808 KB |
Output is correct |
14 |
Correct |
15 ms |
23808 KB |
Output is correct |
15 |
Correct |
14 ms |
23808 KB |
Output is correct |
16 |
Correct |
14 ms |
23808 KB |
Output is correct |
17 |
Correct |
15 ms |
23808 KB |
Output is correct |
18 |
Correct |
14 ms |
23808 KB |
Output is correct |
19 |
Correct |
14 ms |
23808 KB |
Output is correct |
20 |
Correct |
14 ms |
23808 KB |
Output is correct |
21 |
Correct |
15 ms |
23808 KB |
Output is correct |
22 |
Correct |
15 ms |
23808 KB |
Output is correct |
23 |
Correct |
14 ms |
23808 KB |
Output is correct |
24 |
Correct |
14 ms |
23808 KB |
Output is correct |
25 |
Correct |
15 ms |
23808 KB |
Output is correct |
26 |
Correct |
15 ms |
23808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
52284 KB |
Output is correct |
2 |
Correct |
116 ms |
52344 KB |
Output is correct |
3 |
Correct |
109 ms |
52220 KB |
Output is correct |
4 |
Correct |
114 ms |
53308 KB |
Output is correct |
5 |
Correct |
47 ms |
49784 KB |
Output is correct |
6 |
Correct |
50 ms |
49868 KB |
Output is correct |
7 |
Correct |
46 ms |
49912 KB |
Output is correct |
8 |
Correct |
46 ms |
49784 KB |
Output is correct |
9 |
Correct |
50 ms |
50924 KB |
Output is correct |
10 |
Correct |
50 ms |
50668 KB |
Output is correct |
11 |
Correct |
49 ms |
50540 KB |
Output is correct |
12 |
Correct |
48 ms |
49984 KB |
Output is correct |
13 |
Correct |
60 ms |
50160 KB |
Output is correct |
14 |
Correct |
67 ms |
50920 KB |
Output is correct |
15 |
Correct |
103 ms |
52088 KB |
Output is correct |
16 |
Correct |
102 ms |
52088 KB |
Output is correct |
17 |
Correct |
50 ms |
50168 KB |
Output is correct |
18 |
Correct |
51 ms |
50168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
52600 KB |
Output is correct |
2 |
Correct |
116 ms |
52600 KB |
Output is correct |
3 |
Correct |
230 ms |
55648 KB |
Output is correct |
4 |
Correct |
114 ms |
53236 KB |
Output is correct |
5 |
Correct |
577 ms |
50296 KB |
Output is correct |
6 |
Correct |
897 ms |
50296 KB |
Output is correct |
7 |
Correct |
49 ms |
50296 KB |
Output is correct |
8 |
Correct |
655 ms |
50292 KB |
Output is correct |
9 |
Correct |
50 ms |
51820 KB |
Output is correct |
10 |
Correct |
71 ms |
51868 KB |
Output is correct |
11 |
Correct |
283 ms |
52036 KB |
Output is correct |
12 |
Correct |
2067 ms |
51612 KB |
Output is correct |
13 |
Correct |
417 ms |
51952 KB |
Output is correct |
14 |
Correct |
263 ms |
55544 KB |
Output is correct |
15 |
Correct |
227 ms |
53880 KB |
Output is correct |
16 |
Correct |
219 ms |
53880 KB |
Output is correct |
17 |
Correct |
328 ms |
51960 KB |
Output is correct |
18 |
Correct |
339 ms |
51960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
837 ms |
177820 KB |
Output is correct |
2 |
Correct |
828 ms |
177784 KB |
Output is correct |
3 |
Correct |
1156 ms |
183800 KB |
Output is correct |
4 |
Correct |
821 ms |
179188 KB |
Output is correct |
5 |
Correct |
2664 ms |
165536 KB |
Output is correct |
6 |
Execution timed out |
4045 ms |
167616 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |