#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
const int maxl = 25;
const int inf = 1e9;
int n;
int tree[maxn*maxl],lc[maxn*maxl],rc[maxn*maxl],T=1;
void build(int l,int r,int id){
if(l==r) return;
lc[id]=++T;rc[id]=++T;
int mid=(l+r)>>1;
build(l,mid,lc[id]);build(mid+1,r,rc[id]);
}
int update(int l,int r,int id,int p){
if(l==r){
tree[++T]=tree[id]+1;
return T;
}
int mid=(l+r)>>1;
int cc=++T;
lc[cc]=lc[id];rc[cc]=rc[id];
if(p<=mid) lc[cc]=update(l,mid,lc[id],p);
else rc[cc]=update(mid+1,r,rc[id],p);
tree[cc]=tree[lc[cc]]+tree[rc[cc]];
return cc;
}
int query(int l,int r,int id,int tl,int tr){
if(tr<l || r<tl) return 0;
if(tl<=l && r<=tr) return tree[id];
int mid=(l+r)>>1;
return query(l,mid,lc[id],tl,tr)+query(mid+1,r,rc[id],tl,tr);
}
vector<int> e[maxn];
int root[maxn];
void init(int N, int A[], int B[]) {
for(int i=0;i<N;i++) e[B[i]].push_back(A[i]);
n=N;
root[N+1]=1;
build(1,N,1);
for(int i=N;i>=1;i--){
root[i]=root[i+1];
for(int x:e[i]) root[i]=update(1,n,root[i],x);
}
}
int cnt[maxn],dp[maxn];
int can(int M, int K[]) {
vector<int> C;
for(int i=0;i<M;i++){
if(!cnt[K[i]]) C.push_back(K[i]);
cnt[K[i]]+=K[i];
}
auto get = [&](int l,int r){
l=(l==-1?0:C[l]);
r=(r==-1?0:C[r]);
return dp[l]+query(1,n,root[r],l+1,r)-cnt[r];
};
sort(C.begin(),C.end());
vector<pair<int,int>> p;
p.push_back({0,-1});
int sz=(int)C.size();
for(int i=0;i<sz;i++){
/*
int k=upper_bound(p.begin(),p.end(),make_pair(i,inf))-p.begin()-1;
dp[C[i]]=get(p[k].second,i);
if(dp[C[i]]<0){
for(int x:C) cnt[x]=dp[x]=0;
return 0;
}
while(!p.empty()){
auto [x,j]=p.back();
if(i<x && get(j,x)>=get(i,x)) p.pop_back();
else break;
}
auto [l,j]=p.back();
int r=sz;l++;
while(l<r){
int mid=(l+r)>>1;
if(i<mid && get(j,mid)<=get(i,mid)) r=mid;
else l=mid+1;
}
if(r<sz) p.push_back({r,i});
*/
int x=C[i];
dp[x]=inf;
for(int j=max(-1,i-10);j<i;j++) dp[x]=min(dp[x],get(j,i));
if(dp[x]<0){
for(int x:C) cnt[x]=dp[x]=0;
return 0;
}
}
for(int x:C) cnt[x]=dp[x]=0;
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:93:21: warning: declaration of 'x' shadows a previous local [-Wshadow]
93 | for(int x:C) cnt[x]=dp[x]=0;
| ^
teams.cpp:89:13: note: shadowed declaration is here
89 | int x=C[i];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
2 ms |
18776 KB |
Output is correct |
3 |
Correct |
3 ms |
18780 KB |
Output is correct |
4 |
Correct |
3 ms |
18780 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
2 ms |
18780 KB |
Output is correct |
7 |
Correct |
3 ms |
18776 KB |
Output is correct |
8 |
Correct |
3 ms |
18776 KB |
Output is correct |
9 |
Correct |
2 ms |
18780 KB |
Output is correct |
10 |
Correct |
3 ms |
18780 KB |
Output is correct |
11 |
Correct |
3 ms |
18780 KB |
Output is correct |
12 |
Correct |
3 ms |
18776 KB |
Output is correct |
13 |
Correct |
3 ms |
18780 KB |
Output is correct |
14 |
Correct |
3 ms |
18776 KB |
Output is correct |
15 |
Correct |
3 ms |
18780 KB |
Output is correct |
16 |
Correct |
3 ms |
18856 KB |
Output is correct |
17 |
Correct |
3 ms |
18780 KB |
Output is correct |
18 |
Correct |
3 ms |
18780 KB |
Output is correct |
19 |
Correct |
3 ms |
18780 KB |
Output is correct |
20 |
Correct |
3 ms |
18776 KB |
Output is correct |
21 |
Correct |
3 ms |
18780 KB |
Output is correct |
22 |
Correct |
4 ms |
18780 KB |
Output is correct |
23 |
Correct |
3 ms |
18780 KB |
Output is correct |
24 |
Correct |
2 ms |
18780 KB |
Output is correct |
25 |
Correct |
3 ms |
18780 KB |
Output is correct |
26 |
Correct |
3 ms |
18780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
44968 KB |
Output is correct |
2 |
Correct |
32 ms |
44948 KB |
Output is correct |
3 |
Correct |
32 ms |
46992 KB |
Output is correct |
4 |
Correct |
33 ms |
45224 KB |
Output is correct |
5 |
Correct |
18 ms |
43868 KB |
Output is correct |
6 |
Correct |
18 ms |
43868 KB |
Output is correct |
7 |
Correct |
21 ms |
43884 KB |
Output is correct |
8 |
Correct |
17 ms |
44636 KB |
Output is correct |
9 |
Correct |
17 ms |
44500 KB |
Output is correct |
10 |
Correct |
16 ms |
44084 KB |
Output is correct |
11 |
Correct |
17 ms |
44244 KB |
Output is correct |
12 |
Correct |
18 ms |
44236 KB |
Output is correct |
13 |
Correct |
24 ms |
44500 KB |
Output is correct |
14 |
Correct |
25 ms |
47200 KB |
Output is correct |
15 |
Correct |
33 ms |
45908 KB |
Output is correct |
16 |
Correct |
32 ms |
45904 KB |
Output is correct |
17 |
Correct |
20 ms |
44892 KB |
Output is correct |
18 |
Correct |
20 ms |
44644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
45136 KB |
Output is correct |
2 |
Correct |
38 ms |
45140 KB |
Output is correct |
3 |
Correct |
78 ms |
50260 KB |
Output is correct |
4 |
Correct |
32 ms |
45200 KB |
Output is correct |
5 |
Correct |
107 ms |
44112 KB |
Output is correct |
6 |
Correct |
101 ms |
44116 KB |
Output is correct |
7 |
Correct |
23 ms |
44124 KB |
Output is correct |
8 |
Correct |
84 ms |
45392 KB |
Output is correct |
9 |
Correct |
17 ms |
44384 KB |
Output is correct |
10 |
Correct |
17 ms |
44492 KB |
Output is correct |
11 |
Correct |
22 ms |
44744 KB |
Output is correct |
12 |
Correct |
108 ms |
45004 KB |
Output is correct |
13 |
Correct |
135 ms |
45468 KB |
Output is correct |
14 |
Correct |
89 ms |
49036 KB |
Output is correct |
15 |
Correct |
72 ms |
46844 KB |
Output is correct |
16 |
Correct |
69 ms |
46672 KB |
Output is correct |
17 |
Correct |
58 ms |
45396 KB |
Output is correct |
18 |
Correct |
49 ms |
45516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
284 ms |
159824 KB |
Output is correct |
2 |
Correct |
267 ms |
159656 KB |
Output is correct |
3 |
Correct |
449 ms |
167764 KB |
Output is correct |
4 |
Correct |
260 ms |
159828 KB |
Output is correct |
5 |
Correct |
272 ms |
153684 KB |
Output is correct |
6 |
Correct |
248 ms |
153680 KB |
Output is correct |
7 |
Correct |
95 ms |
153752 KB |
Output is correct |
8 |
Correct |
224 ms |
158548 KB |
Output is correct |
9 |
Correct |
99 ms |
157380 KB |
Output is correct |
10 |
Correct |
77 ms |
155588 KB |
Output is correct |
11 |
Correct |
123 ms |
156352 KB |
Output is correct |
12 |
Correct |
330 ms |
157120 KB |
Output is correct |
13 |
Correct |
437 ms |
160196 KB |
Output is correct |
14 |
Correct |
501 ms |
171444 KB |
Output is correct |
15 |
Correct |
305 ms |
165584 KB |
Output is correct |
16 |
Correct |
322 ms |
165592 KB |
Output is correct |
17 |
Correct |
184 ms |
159864 KB |
Output is correct |
18 |
Correct |
179 ms |
159860 KB |
Output is correct |