#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
#define K 100
using namespace std;
struct node{
int l = 0,r = 0;
int val = 0;
}nodes[N * K];
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
int nwnode = ++cnt;
nodes[nwnode] = nodes[v];
if(tl == tr){
nodes[nwnode].val += val;
return nwnode;
}
int tm = (tl + tr)/2;
if(pos <= tm){
if(nodes[v].l == 0){
nodes[v].l = ++cnt;
}
nodes[nwnode].l = upd(nodes[v].l,tl,tm,pos,val);
}
else{
if(nodes[v].r == 0){
nodes[v].r = ++cnt;
}
nodes[nwnode].r = upd(nodes[v].r,tm+1,tr,pos,val);
}
nodes[nwnode].val = nodes[nodes[nwnode].l].val + nodes[nodes[nwnode].r].val;
return nwnode;
}
int get(int v,int tl,int tr,int l,int r){
if(v == 0 || tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return nodes[v].val;
}
int tm = (tl + tr)/2;
return get(nodes[v].l,tl,tm,l,r) + get(nodes[v].r,tm+1,tr,l,r);
}
int root[N];
int n;
vector<int> tmp[N];
void init(int n_, int a[], int b[]) {
n = n_;
for(int i = 0;i<n;i++){
tmp[a[i]].push_back(b[i]);
}
root[0] = upd(1,1,n+1,n+1,n);
for(int i = 1;i<=n+1;i++){
int last = root[i-1];
for(auto u:tmp[i]){
last = upd(last,1,n+1,u,1);
}
last = upd(last,1,n+1,i-1,-get(1,1,n+1,i-1,i-1));
root[i] = last;
}
}
pair<int,int> val[N];
int can(int m, int k[]) {
map<int,int> mp;
sort(k,k+m);
long long sum = 0;
for(int i = 0;i<m;i++){
sum += k[i];
mp[k[i]]++;
}
if(sum > n)return 0;
vector<pair<int,int>> v;
for(auto u:mp){
v.push_back(u);
}
vector<int> st;
for(int x = 0;x<v.size();x++){
int needed = v[x].first * v[x].second;
int tot = 0;
int sum = 0;
int samesum = 0;
int oldsum = 0;
int rp = -1;
int l = v[x].first-1,r = n;
bool ok = 0;
for(int i = st.size()-1;i>=0;i--){
if(val[st[i]].first + 1 < v[x].first)continue;
samesum += val[st[i]].second;
if(rp == -1)rp = st[i];
if(i && val[st[i-1]].first == val[st[i]].first){
continue;
}
if(get(root[v[x].first],1,n+1,v[x].first,val[st[i]].first)- (sum + get(root[rp],1,n+1,l+1,val[st[i]].first) + oldsum) > needed){
int ll = l, rr = val[st[i]].first-1;
while(ll < rr){
int mm = (ll + rr + 1)/2;
if(get(root[v[x].first],1,n+1,v[x].first,mm)- (sum + get(root[rp],1,n+1,l+1,mm) + oldsum) > needed){
rr = mm-1;
}
else ll = mm;
}
l = ll;
ok = 1;
break;
}
sum += oldsum;
sum += get(root[rp],1,n+1,l+1,val[st[i]].first);
l = val[st[i]].first;
oldsum = samesum;
samesum = 0;
rp = -1;
}
if(!ok){
int ll = l, rr = n;
while(ll < rr){
int mm = (ll + rr + 1)/2;
if(get(root[v[x].first],1,n+1,v[x].first,mm)- sum - oldsum> needed){
rr = mm-1;
}
else ll = mm;
}
l = ll;
}
/*
while(l < r){
int m = (l + r + 1)/2;
int now = get(root[v[x].first],1,n+1,v[x].first,m);
for(int i = 0;i<st.size();i++){
if(val[st[i]].first + 1 < v[x].first)break;
if(val[st[i]].first + 1 <= m)
now -= val[st[i]].second;
int p1 = min(val[st[i]].first,m);
int p2 = v[x].first;
if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
if(p1 >= p2)
now -= get(root[st[i]],1,n+1,p2,p1);
}
if(now <= needed){
l = m;
}
else r = m-1;
}*/
tot = get(root[v[x].first],1,n+1,v[x].first,l);
for(int i = 0;i<st.size();i++){
if(val[st[i]].first + 1< v[x].first)break;
if(val[st[i]].first + 1 <= l)
tot -= val[st[i]].second;
int p1 = min(val[st[i]].first,l);
int p2 = v[x].first;
if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
if(p1 >= p2)
tot -= get(root[st[i]],1,n+1,p2,p1);
}
val[v[x].first] = {l,needed-tot};
while(st.size() && val[st.back()].first < val[v[x].first].first){
st.pop_back();
}
st.push_back(v[x].first);
if(val[v[x].first].first == n && val[v[x].first].second)return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int x = 0;x<v.size();x++){
| ~^~~~~~~~~
teams.cpp:79:7: warning: declaration of 'sum' shadows a previous local [-Wshadow]
79 | int sum = 0;
| ^~~
teams.cpp:65:12: note: shadowed declaration is here
65 | long long sum = 0;
| ^~~
teams.cpp:85:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
85 | for(int i = st.size()-1;i>=0;i--){
| ~~~~~~~~~^~
teams.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = 0;i<st.size();i++){
| ~^~~~~~~~~~
teams.cpp:149:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
| ~~~~^~~~~~~~~~~~
teams.cpp:83:24: warning: unused variable 'r' [-Wunused-variable]
83 | int l = v[x].first-1,r = n;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
9 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
12064 KB |
Output is correct |
6 |
Correct |
7 ms |
12028 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
7 ms |
11988 KB |
Output is correct |
9 |
Correct |
9 ms |
12012 KB |
Output is correct |
10 |
Correct |
9 ms |
11988 KB |
Output is correct |
11 |
Correct |
9 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
13 |
Correct |
7 ms |
12116 KB |
Output is correct |
14 |
Correct |
7 ms |
11988 KB |
Output is correct |
15 |
Correct |
7 ms |
12060 KB |
Output is correct |
16 |
Correct |
8 ms |
12068 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
7 ms |
11988 KB |
Output is correct |
19 |
Correct |
9 ms |
11988 KB |
Output is correct |
20 |
Correct |
7 ms |
11988 KB |
Output is correct |
21 |
Correct |
7 ms |
12060 KB |
Output is correct |
22 |
Correct |
7 ms |
12064 KB |
Output is correct |
23 |
Correct |
9 ms |
11988 KB |
Output is correct |
24 |
Correct |
8 ms |
11988 KB |
Output is correct |
25 |
Correct |
10 ms |
12060 KB |
Output is correct |
26 |
Correct |
7 ms |
12068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
58868 KB |
Output is correct |
2 |
Correct |
100 ms |
58876 KB |
Output is correct |
3 |
Correct |
104 ms |
58900 KB |
Output is correct |
4 |
Correct |
114 ms |
59220 KB |
Output is correct |
5 |
Correct |
75 ms |
57756 KB |
Output is correct |
6 |
Correct |
68 ms |
57804 KB |
Output is correct |
7 |
Correct |
66 ms |
57800 KB |
Output is correct |
8 |
Correct |
57 ms |
57744 KB |
Output is correct |
9 |
Correct |
67 ms |
57924 KB |
Output is correct |
10 |
Correct |
68 ms |
56772 KB |
Output is correct |
11 |
Correct |
61 ms |
57900 KB |
Output is correct |
12 |
Correct |
69 ms |
56760 KB |
Output is correct |
13 |
Correct |
77 ms |
57148 KB |
Output is correct |
14 |
Correct |
78 ms |
59388 KB |
Output is correct |
15 |
Correct |
98 ms |
59836 KB |
Output is correct |
16 |
Correct |
102 ms |
59860 KB |
Output is correct |
17 |
Correct |
66 ms |
58784 KB |
Output is correct |
18 |
Correct |
78 ms |
58728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
59252 KB |
Output is correct |
2 |
Correct |
118 ms |
59372 KB |
Output is correct |
3 |
Correct |
998 ms |
62996 KB |
Output is correct |
4 |
Correct |
113 ms |
59268 KB |
Output is correct |
5 |
Correct |
272 ms |
58108 KB |
Output is correct |
6 |
Correct |
199 ms |
58128 KB |
Output is correct |
7 |
Correct |
120 ms |
58236 KB |
Output is correct |
8 |
Correct |
197 ms |
58164 KB |
Output is correct |
9 |
Correct |
67 ms |
57904 KB |
Output is correct |
10 |
Correct |
64 ms |
57044 KB |
Output is correct |
11 |
Correct |
98 ms |
58220 KB |
Output is correct |
12 |
Correct |
371 ms |
57052 KB |
Output is correct |
13 |
Correct |
502 ms |
59048 KB |
Output is correct |
14 |
Correct |
993 ms |
63232 KB |
Output is correct |
15 |
Correct |
347 ms |
60840 KB |
Output is correct |
16 |
Correct |
324 ms |
60784 KB |
Output is correct |
17 |
Correct |
225 ms |
59476 KB |
Output is correct |
18 |
Correct |
231 ms |
59128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
674 ms |
273768 KB |
Output is correct |
2 |
Correct |
780 ms |
273968 KB |
Output is correct |
3 |
Correct |
2902 ms |
283660 KB |
Output is correct |
4 |
Correct |
619 ms |
274268 KB |
Output is correct |
5 |
Correct |
823 ms |
268556 KB |
Output is correct |
6 |
Correct |
703 ms |
268424 KB |
Output is correct |
7 |
Correct |
326 ms |
268436 KB |
Output is correct |
8 |
Correct |
645 ms |
268556 KB |
Output is correct |
9 |
Correct |
312 ms |
267200 KB |
Output is correct |
10 |
Correct |
306 ms |
267236 KB |
Output is correct |
11 |
Correct |
544 ms |
267300 KB |
Output is correct |
12 |
Correct |
1112 ms |
267588 KB |
Output is correct |
13 |
Correct |
1681 ms |
275392 KB |
Output is correct |
14 |
Correct |
3196 ms |
287276 KB |
Output is correct |
15 |
Correct |
1063 ms |
279692 KB |
Output is correct |
16 |
Correct |
1103 ms |
279592 KB |
Output is correct |
17 |
Correct |
727 ms |
273976 KB |
Output is correct |
18 |
Correct |
744 ms |
274116 KB |
Output is correct |