답안 #56287 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56287	2018-07-11T02:13:48 Z	Diuven	Growing Trees (BOI11_grow)	C++11	100 / 100	235 ms	3660 KB

grow

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, q;

struct node {
  int mx, lz;
} tree[4*MX];


int A[MX];

void busy(int v, int s, int e){
  int &z=tree[v].lz;
  if(s!=e){
    node &nd1=tree[v*2], &nd2=tree[v*2+1];
    nd1.lz+=z, nd2.lz+=z;
    nd1.mx+=z, nd2.mx+=z;
  }
  z=0;
}
void upt(int v, int s, int e, int l, int r, int val){
  if(e<l || r<s) return;
  node &nd=tree[v];
  if(l<=s && e<=r){
    nd.lz+=val;
    nd.mx+=val;
    return;
  }
  busy(v,s,e);
  upt(v*2,s,(s+e)/2,l,r,val);
  upt(v*2+1,(s+e)/2+1,e,l,r,val);
  nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void upt(int l, int r, int val){
  if(r<l) return;
  upt(1,1,n,l,r,val);
}
int lb(int v, int s, int e, int h){
  busy(v,s,e);
  if(s==e) return s;
  if(tree[v*2].mx>=h) return lb(v*2,s,(s+e)/2,h);
  else return lb(v*2+1,(s+e)/2+1,e,h);
}
int lb(int h){
  if(tree[1].mx<h) return n+1;
  return lb(1,1,n,h);
}
int val(int v, int s, int e, int pos){
  if(pos<s || e<pos) return 0;
  busy(v,s,e);
  if(s==e) return tree[v].mx;
  return val(v*2,s,(s+e)/2,pos) + val(v*2+1,(s+e)/2+1,e,pos);
}
int val(int pos){
  return val(1,1,n,pos);
}

int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>n>>q;
  for(int i=1; i<=n; i++){
    cin>>A[i];
  }
  sort(A+1, A+n+1);
  for(int i=1; i<=n; i++){
    upt(i, i, A[i]);
  }

  for(int i=1; i<=q; i++){
    char o; int x, y; cin>>o>>x>>y;
    // for(int i=1; i<=n; i++) cout<<val(i)<<' ';
    // cout<<'\n';
    if(o=='F'){
      int l=lb(y); // l부터 x개
      if(l==n+1) continue;
      x=min(x, n-l+1);
      int v=val(l+x-1);

      int a=lb(v)-1;
      upt(l,a,1); x-=(a-l+1);

      int r=lb(v+1)-1;
      upt(r-x+1,r,1);
    }
    else{
      int l=lb(x), r=lb(y+1);
      cout<<r-l<<'\n';
    }
  }
  return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	130 ms	2936 KB	Output is correct
2	Correct	211 ms	2936 KB	Output is correct
3	Correct	170 ms	2936 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2936 KB	Output is correct
2	Correct	5 ms	2936 KB	Output is correct
3	Correct	4 ms	2936 KB	Output is correct
4	Correct	4 ms	2936 KB	Output is correct
5	Correct	68 ms	2936 KB	Output is correct
6	Correct	86 ms	2936 KB	Output is correct
7	Correct	12 ms	2936 KB	Output is correct
8	Correct	45 ms	2936 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	2936 KB	Output is correct
2	Correct	73 ms	2936 KB	Output is correct
3	Correct	6 ms	2936 KB	Output is correct
4	Correct	53 ms	2936 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	94 ms	2936 KB	Output is correct
2	Correct	78 ms	2936 KB	Output is correct
3	Correct	16 ms	2936 KB	Output is correct
4	Correct	73 ms	2936 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	2936 KB	Output is correct
2	Correct	188 ms	3128 KB	Output is correct
3	Correct	23 ms	3128 KB	Output is correct
4	Correct	121 ms	3128 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	144 ms	3280 KB	Output is correct
2	Correct	136 ms	3280 KB	Output is correct
3	Correct	128 ms	3280 KB	Output is correct
4	Correct	21 ms	3280 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	101 ms	3280 KB	Output is correct
2	Correct	120 ms	3284 KB	Output is correct
3	Correct	165 ms	3284 KB	Output is correct
4	Correct	21 ms	3284 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	160 ms	3284 KB	Output is correct
2	Correct	142 ms	3284 KB	Output is correct
3	Correct	64 ms	3284 KB	Output is correct
4	Correct	118 ms	3296 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	153 ms	3380 KB	Output is correct
2	Correct	147 ms	3380 KB	Output is correct
3	Correct	235 ms	3380 KB	Output is correct

Subtask #10
10.0 / 10.0

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

답안 #56287

Compilation message