#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+6;
int n;
int a[MAXN];
int b[MAXN];
struct node
{
int val;
node *l, *r;
node(int x){
val=x;
l=nullptr;
r=nullptr;
}
node(node *_l,node *_r)
{
l=_l;
r=_r;
val=0;
if(l)val+=l->val;
if(r)val+=r->val;
}
node(node *t)
{
val=t->val;
l=t->l;
r=t->r;
}
};
node *update(node *t,int val,int pos,int l=1,int r=n)
{
//cerr<<"update "<<l<<" "<<r<<endl;
if(l==r)return new node(val);
int mid=(l+r)/2;
if(pos>mid)
{
if(t==nullptr)return new node(nullptr, update(nullptr,val,pos, mid+1,r));
else return new node(t->l, update(t->r,val,pos, mid+1,r));
}
else
{
if(t==nullptr)return new node(update(nullptr,val,pos,l,mid), nullptr);
else return new node(update(t->l,val,pos,l,mid), t->r);
}
}
int query(node *t,int ql,int qr,int l=1,int r=n)
{
//cerr<<"query "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
if(ql>r)return 0;
if(t==nullptr)return 0;
if(qr<l)return 0;
if(l>=ql&&r<=qr)return t->val;
int mid=(l+r)/2;
return query(t->l,ql,qr,l,mid)+query(t->r,ql,qr,mid+1,r);
}
node *roots[MAXN];
struct segment
{
int l,r;
};
vector<segment>v;
bool cmp(segment s1,segment s2)
{
if(s1.r!=s2.r)return s1.r<s2.r;
else return s1.l<s2.l;
}
vector<segment>s1[MAXN];
int sum[MAXN];
void init(int N, int A[], int B[]) {
n=N;
for(int i=0;i<N;i++)
{
a[i]=A[i];
b[i]=B[i];
v.push_back({A[i],B[i]});
}
sort(v.rbegin(),v.rend(),cmp);
for(auto xd:v)
{
s1[xd.r].push_back(xd);
}
roots[n+1]=nullptr;
for(int i=n;i>=1;i--)
{
roots[i]=roots[i+1];
//cout<<"???\n";
{
for(auto xd:s1[i])
{
++sum[xd.l];
roots[i]=update(roots[i],sum[xd.l],xd.l,1,n);
//cerr<<" "<<xd.l<<" ^^"<<endl;
}
}
}
}
int m;
int k[MAXN];
int dp[MAXN];
int get_value1(int x)
{
node* root_we_need = roots[x];
return query(root_we_need,1,x,1,n);
}
int get_value(int i1,int i2)
{
if(k[i1]+1>k[i2])return 0;
//should return no. of segments with k[i2]>=l>k[i1] and r>=k[i2]
//persistent segment tree can do :(
node *root_we_need = roots[k[i2]];
return query(root_we_need, k[i1]+1,k[i2],1,n);
}
int can(int M, int K[]) {
//cerr<<"========query=========";
sort(K,K+M);
int sumk=0;
for(int i=0;i<M;i++)
{
k[i]=K[i];
sumk+=k[i];
}
if(sumk>n)return 0;
m=M;
dp[0]=get_value1(K[0])-K[0];
if(dp[0]<0)return 0;
vector<int>ids;
ids.push_back(0);
//cerr<<"0 : "<<dp[0]<<endl;
for(int i=1;i<m;i++)
{
while(ids.size()>1)
{
int id1=ids[ids.size()-2];
int id2=ids[ids.size()-1];
if(get_value(id1, i)+dp[id1]<=get_value(id2, i)+dp[id2])
{
ids.pop_back();
}
else
{
break;
}
}
dp[i]=min(dp[ids.back()]+get_value(ids.back(), i)-K[i],get_value1(K[i])-K[i]);
//cerr<<i<<" : "<<dp[i]<<endl;
if(dp[i]<0)return 0;
ids.push_back(i);
}
return 1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
8 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
12008 KB |
Output is correct |
4 |
Correct |
7 ms |
12116 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
7 ms |
12116 KB |
Output is correct |
7 |
Correct |
6 ms |
12116 KB |
Output is correct |
8 |
Correct |
6 ms |
12116 KB |
Output is correct |
9 |
Correct |
6 ms |
12116 KB |
Output is correct |
10 |
Correct |
6 ms |
12120 KB |
Output is correct |
11 |
Correct |
6 ms |
12116 KB |
Output is correct |
12 |
Correct |
7 ms |
12116 KB |
Output is correct |
13 |
Correct |
7 ms |
12124 KB |
Output is correct |
14 |
Correct |
7 ms |
12116 KB |
Output is correct |
15 |
Correct |
7 ms |
12116 KB |
Output is correct |
16 |
Correct |
8 ms |
12132 KB |
Output is correct |
17 |
Correct |
8 ms |
11988 KB |
Output is correct |
18 |
Correct |
7 ms |
11988 KB |
Output is correct |
19 |
Correct |
7 ms |
12036 KB |
Output is correct |
20 |
Correct |
6 ms |
11988 KB |
Output is correct |
21 |
Correct |
7 ms |
11988 KB |
Output is correct |
22 |
Correct |
7 ms |
12056 KB |
Output is correct |
23 |
Correct |
6 ms |
11988 KB |
Output is correct |
24 |
Correct |
6 ms |
12100 KB |
Output is correct |
25 |
Correct |
6 ms |
11988 KB |
Output is correct |
26 |
Correct |
7 ms |
11988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
126 ms |
72904 KB |
Output is correct |
2 |
Correct |
115 ms |
72936 KB |
Output is correct |
3 |
Correct |
119 ms |
72940 KB |
Output is correct |
4 |
Correct |
124 ms |
73736 KB |
Output is correct |
5 |
Correct |
79 ms |
71640 KB |
Output is correct |
6 |
Correct |
79 ms |
71632 KB |
Output is correct |
7 |
Correct |
83 ms |
71712 KB |
Output is correct |
8 |
Correct |
82 ms |
71680 KB |
Output is correct |
9 |
Correct |
81 ms |
73116 KB |
Output is correct |
10 |
Correct |
82 ms |
72676 KB |
Output is correct |
11 |
Correct |
74 ms |
72372 KB |
Output is correct |
12 |
Correct |
74 ms |
72256 KB |
Output is correct |
13 |
Correct |
83 ms |
71904 KB |
Output is correct |
14 |
Correct |
85 ms |
72840 KB |
Output is correct |
15 |
Correct |
110 ms |
72740 KB |
Output is correct |
16 |
Correct |
105 ms |
72868 KB |
Output is correct |
17 |
Correct |
81 ms |
72668 KB |
Output is correct |
18 |
Correct |
90 ms |
72696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
121 ms |
73356 KB |
Output is correct |
2 |
Correct |
120 ms |
73272 KB |
Output is correct |
3 |
Correct |
182 ms |
76236 KB |
Output is correct |
4 |
Correct |
117 ms |
73696 KB |
Output is correct |
5 |
Correct |
134 ms |
72020 KB |
Output is correct |
6 |
Correct |
121 ms |
72020 KB |
Output is correct |
7 |
Correct |
85 ms |
72120 KB |
Output is correct |
8 |
Correct |
135 ms |
72020 KB |
Output is correct |
9 |
Correct |
80 ms |
73056 KB |
Output is correct |
10 |
Correct |
84 ms |
73056 KB |
Output is correct |
11 |
Correct |
97 ms |
72756 KB |
Output is correct |
12 |
Correct |
126 ms |
72660 KB |
Output is correct |
13 |
Correct |
168 ms |
72364 KB |
Output is correct |
14 |
Correct |
225 ms |
76512 KB |
Output is correct |
15 |
Correct |
151 ms |
74712 KB |
Output is correct |
16 |
Correct |
142 ms |
74772 KB |
Output is correct |
17 |
Correct |
132 ms |
74524 KB |
Output is correct |
18 |
Correct |
119 ms |
74560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
761 ms |
352696 KB |
Output is correct |
2 |
Correct |
792 ms |
352708 KB |
Output is correct |
3 |
Correct |
1034 ms |
358568 KB |
Output is correct |
4 |
Correct |
739 ms |
353396 KB |
Output is correct |
5 |
Correct |
511 ms |
346084 KB |
Output is correct |
6 |
Correct |
535 ms |
346140 KB |
Output is correct |
7 |
Correct |
439 ms |
346164 KB |
Output is correct |
8 |
Correct |
528 ms |
346104 KB |
Output is correct |
9 |
Correct |
397 ms |
348344 KB |
Output is correct |
10 |
Correct |
400 ms |
345772 KB |
Output is correct |
11 |
Correct |
439 ms |
345464 KB |
Output is correct |
12 |
Correct |
533 ms |
345512 KB |
Output is correct |
13 |
Correct |
721 ms |
346020 KB |
Output is correct |
14 |
Correct |
1014 ms |
362692 KB |
Output is correct |
15 |
Correct |
732 ms |
358600 KB |
Output is correct |
16 |
Incorrect |
721 ms |
358668 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |