# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
991015 |
2024-06-01T04:13:55 Z |
User0069 |
Teams (IOI15_teams) |
C++17 |
|
2789 ms |
524288 KB |
#include<bits/stdc++.h>
#include"teams.h"
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=5e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int N;
struct node
{
node *l,*r;
int val;
node():l(NULL),r(NULL),val(0){};
};
node* root[maxn];
vector<int> v[maxn];
node* cons(node* kk,int cl,int cr)
{
kk=new node();
if(cl==cr)
{
return kk;
}
int mid=(cl+cr)/2;
kk->l=cons(kk->l,cl,mid);
kk->r=cons(kk->r,mid+1,cr);
return kk;
}
node* update(node* kk,int cl,int cr,int pos,int val)
{
node* kkk=new node();
kkk->l=kk->l;
kkk->r=kk->r;
kkk->val=kk->val;
if(cl==cr)
{
kkk->val+=val;
return kkk;
}
int mid=(cl+cr)/2;
if(pos<=mid) kkk->l=update(kk->l,cl,mid,pos,val);
else kkk->r=update(kk->r,mid+1,cr,pos,val);
kkk->val=kkk->l->val+kkk->r->val;
return kkk;
}
int get(node* kk,int cl,int cr,int l,int r )
{
if(cl>r||cr<l) return 0;
if(cl>=l&&cr<=r) return kk->val;
int mid=(cl+cr)/2;
return get(kk->l,cl,mid,l,r)+get(kk->r,mid+1,cr,l,r);
}
int cnt(int a,int b,int c,int d)
{
return get(root[b],0,N,c,d)-get(root[a-1],0,N,c,d);
}
void init(int32_t n,int32_t* a,int32_t* b)
{
N=n;
root[0]=cons(root[0],0,n);
for(int i=0;i<n;i++)
{
v[b[i]].push_back(a[i]);
}
for(int i=1;i<=n;i++)
{
root[i]=root[i-1];
for(int x:v[i])
{
root[i]=update(root[i],0,n,x,1);
}
}
root[n+1]=root[n];
}
struct ele
{
int a,b,range,rmd;
};
int32_t can(int32_t m,int32_t* k)
{
sort(k,k+m);
vector<int> v;
vector<ele> st;
st.push_back({0,0,N,0});
for(int i=0;i<m;i++)
{
int prev,late,a,b,sum=0;
a=k[i];
if(i==0) prev=0;
else prev=k[i-1];
if(i==m-1) late=N+1;
else late=k[i+1];
b=prev+1;
int wa,ra=k[i]-1;
int lmao;
while(!st.empty()&&sum+(lmao=cnt(ra+1,st.back().range,b,k[i]))+st.back().rmd<k[i])
{
b=st.back().b;
sum+=lmao;
ra=st.back().range;
st.pop_back();
}
if(st.empty()) return 0;
int l=ra+1,r=st.back().range,ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(sum+cnt(ra+1,mid,b,k[i])>=k[i])
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
st.push_back({a,b,ans,sum+cnt(ra+1,ans,b,k[i])-k[i]});
}
return 1;
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// int n,q;
// cin>>n>>q;
// int32_t _a[n],_b[n];
// for(int i=1;i<=n;i++)
// {
// cin>>_a[i]>>_b[i];
// }
// init(n,_a,_b);
// while(q--)
// {
// int32_t _m;
// cin>>_m;
// int32_t _k[_m];
// for(int i=0;i<_m;i++)
// {
// cin>>_k[i];
// }
// cout<<can(_m,_k)<<"\n";
// }
//}
Compilation message
teams.cpp: In function 'int32_t can(int32_t, int32_t*)':
teams.cpp:93:17: warning: declaration of 'v' shadows a global declaration [-Wshadow]
93 | vector<int> v;
| ^
teams.cpp:27:13: note: shadowed declaration is here
27 | vector<int> v[maxn];
| ^
teams.cpp:98:18: warning: variable 'late' set but not used [-Wunused-but-set-variable]
98 | int prev,late,a,b,sum=0;
| ^~~~
teams.cpp:105:13: warning: unused variable 'wa' [-Wunused-variable]
105 | int wa,ra=k[i]-1;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12892 KB |
Output is correct |
2 |
Correct |
2 ms |
12892 KB |
Output is correct |
3 |
Correct |
2 ms |
12892 KB |
Output is correct |
4 |
Correct |
2 ms |
13144 KB |
Output is correct |
5 |
Correct |
2 ms |
12892 KB |
Output is correct |
6 |
Correct |
3 ms |
12944 KB |
Output is correct |
7 |
Correct |
3 ms |
12972 KB |
Output is correct |
8 |
Correct |
4 ms |
12892 KB |
Output is correct |
9 |
Correct |
3 ms |
12892 KB |
Output is correct |
10 |
Correct |
3 ms |
12892 KB |
Output is correct |
11 |
Runtime error |
10 ms |
25692 KB |
Execution killed with signal 11 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
80364 KB |
Output is correct |
2 |
Correct |
101 ms |
80468 KB |
Output is correct |
3 |
Correct |
104 ms |
80328 KB |
Output is correct |
4 |
Correct |
117 ms |
80996 KB |
Output is correct |
5 |
Correct |
67 ms |
79188 KB |
Output is correct |
6 |
Correct |
66 ms |
79188 KB |
Output is correct |
7 |
Correct |
69 ms |
79184 KB |
Output is correct |
8 |
Correct |
68 ms |
79164 KB |
Output is correct |
9 |
Runtime error |
156 ms |
161280 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
81232 KB |
Output is correct |
2 |
Correct |
99 ms |
81232 KB |
Output is correct |
3 |
Correct |
695 ms |
84564 KB |
Output is correct |
4 |
Correct |
95 ms |
80980 KB |
Output is correct |
5 |
Correct |
392 ms |
79956 KB |
Output is correct |
6 |
Correct |
380 ms |
79864 KB |
Output is correct |
7 |
Correct |
73 ms |
80008 KB |
Output is correct |
8 |
Correct |
279 ms |
79956 KB |
Output is correct |
9 |
Runtime error |
126 ms |
161088 KB |
Execution killed with signal 11 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
381696 KB |
Output is correct |
2 |
Correct |
632 ms |
381524 KB |
Output is correct |
3 |
Correct |
2789 ms |
388356 KB |
Output is correct |
4 |
Correct |
612 ms |
381204 KB |
Output is correct |
5 |
Correct |
1201 ms |
374248 KB |
Output is correct |
6 |
Correct |
1076 ms |
374444 KB |
Output is correct |
7 |
Correct |
344 ms |
374352 KB |
Output is correct |
8 |
Correct |
1058 ms |
374408 KB |
Output is correct |
9 |
Runtime error |
2671 ms |
524288 KB |
Execution killed with signal 9 |
10 |
Halted |
0 ms |
0 KB |
- |