oj.uz

Submission #701775

# Submission time Handle Problem Language Result Execution time Memory
701775 2023-02-22T05:44:33 Z EthanKim8683 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 222 ms 76088 KB 
#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
using B=bool;
const I Q=1e5;
const I LOGP=30;
const Lli FIXP=1ll<<LOGP;
I chds[2*LOGP*Q+1][2];
Lli vals[2*LOGP*Q+1];
B dels[2*LOGP*Q+1];
I t=1;
void psh(Lli low,Lli upp,I j){
  if(upp-low>1){
    chds[j][0]=chds[j][0]?:++t,chds[j][1]=chds[j][1]?:++t;
    if(dels[j])vals[chds[j][0]]=vals[chds[j][1]]=(upp-low)/2;
    dels[chds[j][0]]|=dels[j],dels[chds[j][1]]|=dels[j];
  }
  dels[j]=0;
}
void pll(Lli low,Lli upp,I j){
  vals[j]=vals[chds[j][0]]+vals[chds[j][1]];
}
void upd(Lli l,Lli r,Lli low=0,Lli upp=FIXP,I j=1){
  if(l>=upp||r<=low)return;
  if(l<=low&&r>=upp){vals[j]=upp-low,dels[j]=1;return;}
  Lli mid=low+(upp-low)/2;
  psh(low,upp,j);
  upd(l,r,low,mid,chds[j][0]=chds[j][0]?:++t);
  upd(l,r,mid,upp,chds[j][1]=chds[j][1]?:++t);
  pll(low,upp,j);
}
Lli qry(Lli l,Lli r,Lli low=0,Lli upp=FIXP,I j=1){
  if(l>=upp||r<=low)return 0;
  if(l<=low&&r>=upp)return vals[j];
  Lli mid=low+(upp-low)/2;
  psh(low,upp,j);
  Lli res=0;
  res+=qry(l,r,low,mid,chds[j][0]=chds[j][0]?:++t);
  res+=qry(l,r,mid,upp,chds[j][1]=chds[j][1]?:++t);
  return res;
}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I m;cin>>m;
  Lli c=0;
  while(m--){
    I d;cin>>d;
    if(d==1){
      Lli x,y;cin>>x>>y;
      c=qry(x+c,y+c+1);
      printf("%lli\n",c);
    }
    if(d==2){
      Lli x,y;cin>>x>>y;
      upd(x+c,y+c+1);
    }
  }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 2004 KB Output is correct
5 Correct 11 ms 2260 KB Output is correct
6 Correct 11 ms 2212 KB Output is correct
7 Correct 11 ms 2336 KB Output is correct
8 Correct 73 ms 16404 KB Output is correct
9 Correct 184 ms 28812 KB Output is correct
10 Correct 167 ms 32244 KB Output is correct
11 Correct 183 ms 34548 KB Output is correct
12 Correct 193 ms 35540 KB Output is correct
13 Correct 157 ms 41132 KB Output is correct
14 Correct 162 ms 41556 KB Output is correct
15 Correct 209 ms 74004 KB Output is correct
16 Correct 209 ms 74532 KB Output is correct
17 Correct 156 ms 42832 KB Output is correct
18 Correct 156 ms 42904 KB Output is correct
19 Correct 218 ms 76088 KB Output is correct
20 Correct 222 ms 76044 KB Output is correct