# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
226577 | MKopchev | Growing Trees (BOI11_grow) | C++14 | 149 ms | 3832 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;
int n,q;
int inp[nmax];
long long pref[nmax];
void update(int pos,int val)
{
//cout<<"update "<<pos<<" "<<val<<endl;
while(pos<=n)
{
pref[pos]+=val;
pos=pos+(pos&(-pos));
}
}
void update_interval(int l,int r,int val)
{
//cout<<"update_interval "<<l<<" "<<r<<" "<<val<<endl;
update(l,val);
update(r+1,-val);
}
int query(int pos)
{
//cout<<"query "<<pos<<endl;
long long ret=0;
while(pos)
{
ret=ret+pref[pos];
pos=pos-(pos&(-pos));
}
return ret;
}
int where_begins(int val)
{
int not_ok=0,ok=n+1;
while(ok-not_ok>1)
{
int av=(ok+not_ok)/2;
if(query(av)>val)not_ok=av;
else ok=av;
}
//cout<<"where_begins "<<val<<" -> "<<ok<<endl;
return ok;
}
int main()
{
scanf("%i%i",&n,&q);
for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
sort(inp+1,inp+n+1);
reverse(inp+1,inp+n+1);
for(int i=1;i<=n;i++)
update_interval(i,i,inp[i]);
for(int i=1;i<=q;i++)
{
char c=getchar();
while(c!='F'&&c!='C')c=getchar();
if(c=='C')
{
int mini,maxi;
scanf("%i%i",&mini,&maxi);
printf("%i\n",where_begins(mini-1)-where_begins(maxi));
}
else
{
int height,cnt;
scanf("%i%i",&cnt,&height);
int pos=where_begins(height-1);
pos--;
if(pos<=cnt)
{
update_interval(1,pos,1);
continue;
}
int max_applied=query(pos-cnt+1);
int start=where_begins(max_applied);
int pos_other=where_begins(max_applied-1);
//cout<<pos<<" "<<start<<" "<<max_applied<<" "<<pos_other<<endl;
update_interval(pos_other,pos,1);
cnt=cnt-(pos-pos_other+1);
update_interval(start,start+cnt-1,1);
}
/*
for(int j=1;j<=n;j++)
cout<<query(j)<<" ";cout<<endl;
*/
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |