oj.uz

답안 #751280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751280 2023-05-31T10:45:35 Z amin Growing Trees (BOI11_grow) C++14
40 / 100
 172 ms 3268 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int seg[1000000];
int laz[1000000];
int a[1000003];
int z;
int b[1000003];
int ans=0;
int n;
void merg(int v,int v1,int v2)
{

  seg[v]=max(seg[v1],seg[v2]);


}
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        seg[v]=a[tl];
        return ;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    merg(v,v*2,v*2+1);
}

void push(int v)
{
    laz[v*2]+=laz[v];
    seg[v*2]+=laz[v];
    seg[v*2+1]+=laz[v];
    laz[v*2+1]+=laz[v];
    laz[v]=0;
}
void update(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return ;
    if(tl==l&&tr==r)
    {
      seg[v]++;
      laz[v]++;

        return ;

    }
    push(v);
    int tm=(tl+tr)>>1;
   update(v*2,tl,tm,l,min(r,tm));
   update(v*2+1,tm+1,tr,max(tm+1,l),r);
    merg(v,v*2,v*2+1);

}
int get(int v,int tl,int tr,int val)
{
    //cout<<tl<<' '<<tr<<endl;
   /* if(val<tl||val>tr)
        return 1000000;*/
     //   cout<<tl<<' '<<tr<<endl;
 if(tl==tr)
 {
     //cout<<seg[v]<<endl;
     return tl;
 }
push(v);
int tm=(tl+tr)/2;
if(seg[v*2]>=val)
{
    return get(v*2,tl,tm,val);
}else
return get(v*2+1,tm+1,tr,val);

}
int get1(int v,int tl,int tr,int pos)
{
  //  cout<<tl<<' '<<tr<<' '<<pos<<endl;
    if(pos<tl||pos>tr)
        return n;
    if(tl==tr)
        return seg[v];
    int tm=(tl+tr)>>1;
    push(v);
    return min(get1(v*2,tl,tm,pos),get1(v*2+1,tm+1,tr,pos));

}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //  freopen("balancing.in","r",stdin);
   // freopen("balancing.out","w",stdout);

cin>>n;
int q;
cin>>q;

for(int i=0;i<n;i++)
{
    cin>>a[i];
}
sort(a,a+n);
a[n]=1500000000;
build(1,0,n);
while(q--)
{
    char c;

    cin>>c;
        int co,mi;
    cin>>mi>>co;
    swap(mi,co);
    if(c=='F')
    {

  //  co--;
    int pos=get(1,0,n,mi);
    int en=pos+co-1;
    en=min(en,n-1);
    if(en==n-1)
    {
        update(1,0,n,pos,n-1);
        continue;
    }
    int val=get1(1,0,n,en);
    int st=get(1,0,n,val);
    int e=get(1,0,n,val+1);
    update(1,0,n,pos,st-1);
 //   cout<<pos<<' '<<st-1<<' '<<e-en+st-1<<' '<<e-1<<endl;
    update(1,0,n,e-(en-st+1),e-1);
    /*for(int y=0;y<n;y++)
    {
        cout<<get1(1,0,n,y)<<' ';
    }
    cout<<endl;*/

    }else
    {
        swap(mi,co);
      //  cout<<get(1,0,n,co+1)<<get(1,0,n,mi);
   // cout<<mi<<' '<<co+1<<endl;
        cout<<get(1,0,n,co+1)-get(1,0,n,mi)<<endl;
    }
}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 2952 KB Output is correct
2 Incorrect 142 ms 2840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Incorrect 112 ms 692 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 784 KB Output is correct
2 Incorrect 137 ms 836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 864 KB Output is correct
2 Correct 157 ms 892 KB Output is correct
3 Correct 11 ms 468 KB Output is correct
4 Incorrect 153 ms 744 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 1800 KB Output is correct
2 Correct 134 ms 2836 KB Output is correct
3 Correct 34 ms 980 KB Output is correct
4 Correct 41 ms 2668 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 2784 KB Output is correct
2 Correct 133 ms 2872 KB Output is correct
3 Correct 59 ms 2640 KB Output is correct
4 Correct 35 ms 980 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 2836 KB Output is correct
2 Correct 115 ms 2968 KB Output is correct
3 Correct 51 ms 2696 KB Output is correct
4 Correct 31 ms 980 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 135 ms 2872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 3000 KB Output is correct
2 Incorrect 134 ms 2764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 3268 KB Output is correct