Submission #535128

#	Time	Username	Problem	Language	Result	Execution time	Memory
535128		MR2211	Growing Trees (BOI11_grow)	C++14	0 / 100	114 ms	8516 KiB

grow

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define endl '\n'
#define pb push_back
#define lb(a,x) (lower_bound(be(a),x)-a.begin())
#define ub(a,x) (upper_bound(be(a),x)-a.begin())
#define fast ios::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define precision cout << setprecision(4) << setiosflags(ios::fixed) << setiosflags(ios::showpoint);
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;
#define Case(tt) cout<<"Case "<<tt<<": ";
#define mid (s+e)/2
//#difene 2*p 2*p
#define ri 2*p+1
using namespace std;
int n,q,a,b,lazy[400040];
vector<ll>v;
pair<ll,ll>st[400040];
char c;
pair<ll,ll> mer(int f,int s)
{
//    push(p,s,e);
    return {max(st[f].ff,st[s].ff),min(st[f].ss,st[s].ss)};
}
void push(int p,int s,int e)
{
//    if(lazy[p]==-1)return ;
    st[p].ff+=lazy[p];
    st[p].ss+=lazy[p];
    if(s!=e)lazy[2*p]+=lazy[p],lazy[ri]+=lazy[p];
    lazy[p]=0;
}
void prin(int p,int s,int e)
{
    push(p,s,e);
    if(s==e){
        cout<<st[p].ss<<' ';
        return ;
    }
    prin(2*p,s,mid);
    prin(ri,mid+1,e);

}
void build(int p, int s,int e)
{
    if(s==e){
        st[p]={v[s],v[s]};
        return;
    }
    build(2*p,s,mid);
    build(ri,mid+1,e);
    st[p]=mer(2*p,ri);
}
//int bin(int k)
//{
//    int l=0,h=n-1,md,ans=0;
//    while(l<=h)
//    {
//        md=(l+h)/2;
//        if(v[md]>=k)ans=md,md=h-1;
//        else md=l+1;
//    }
//    return ans;
//}
//int bin2(int k)
//{
//    int l=0,h=n-1,md,ans=0;
//    while(l<=h)
//    {
//        md=(l+h)/2;
//        if(v[md]<=k)
//            ans=md,md=l+1;
//        else md=h-1;
//    }
//    return ans;
//}
ll getl(int p,int s,int e,int k)
{
    push(p,s,e);
    if(s==e)return s;
    if(st[2*p].ff>=k)
        return getl(2*p,s,mid,k);
    else if (st[ri].ff<k)return-1;
    else return getl(ri,mid+1,e,k);
}
ll getr(int p,int s,int e,int k)
{
    push(p,s,e);
    if(s==e)return s;
    if(st[ri].ss<=k)
        return getr(ri,mid+1,e,k);
    else
        return getr(2*p,s,mid,k);
}
ll getval(int p,int s,int e,int i)
{
    push(p,s,e);
   if(s==e)return st[p].ff;
    if(i<=mid)return getval(2*p,s,mid,i);
    else return getval(ri,mid+1,e,i);
}
void update(int p,int s,int e,int l,int r)
{
    push(p,s,e);
    if(s>r || e<l)return;
    if(s>=l && e<=r){
            lazy[p]+=1;
    return;
    }
    update(2*p,s,mid,l,r);
    update(ri,mid+1,e,l,r);
    st[p]=mer(2*p,ri);
}
ll get(int p , int s,int e ,int l ,int r)
{
    push(p,s,e);
    if(st[p].ff<=r && st[p].ss>=l)return e-s+1;
    if(st[p].ff<l || st[p].ss>r)return 0;
    return get(2*p,s,mid,l,r)+get(ri,mid+1,e,l,r);
}
int main()
{
    fast
    cin>>n>>q;
    v.resize(n);
    for(int i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end());
    build(1,0,n-1);
//    cout<<st[1].ff<<' '<<st[1].ss<<endl;
    for(int i=0;i<q; ++i)
    {
        cin>>c>>a>>b;
        if(c=='g'){
                prin(1,0,n-1);
                cout<<endl;
        continue;
        }
        if(c=='F'){
            int left=getl(1,0,n-1,b);
//            cout<<left<<endl;
            if(left==-1)continue;
            if(a>=n-left)update(1,0,n-1,left,n-1);
            else {
//                    cout<<"FUCK"<<endl;
                ll val = getval(1,0,n-1,left + a-1);
                int l=getl(1,0,n-1,val);
                int r=getr(1,0,n-1,val);
                update(1,0,n-1,r-(a-(l-left))+1,r);
//                cout<<val<<' '<<l<<' '<<r<<endl;
//cout<<left <<' '<<l<<' '<<r<<endl;
//            cout<<"FUCK"<<endl;
                if(l!=left)
                update(1,0,n-1,left,l-1);
            }
        }
        else cout<<get(1,0,n-1,a,b)<<endl;
    }
    return 0;
}
//5 1000
//1 3 2 5 2

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10