Submission #799605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
799605	2023-07-31T16:31:41 Z	bxolqctwhytewwwsqc	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KB

apple

using namespace std;
#include <bits/stdc++.h>

#define i64 long long
#define u32 unsigned int
#define u64 unsigned long long 
#define f32 float
#define f64 double
#define vec vector
#define F0R(i, e) for(i64 i = 0; i<e; i++)
#define FOR(i, s, e) for(i64 i = s; i<e; i++)
#define F0Rd(i, e) for(i64 i = e-1; i>=0; i--)
#define FORd(i, s, e) for(i64 i = e-1; i>=s; i--)
#define TRAV(v, g) for(auto v: g)

const i64 INF_32 = INT32_MAX/3;
const i64 INF_64 = INT64_MAX/3;

struct SegNode {
  i64 ll=0, rr=1e9+5;
  i64 cnt = 0;
  SegNode *left=nullptr, *right=nullptr;
  
  i64 update(i64 l, i64 r) {
    if(ll >= r || rr <= l || cnt == rr-ll) {
      return 0;
    }
    if(l<=ll && r>=rr) {
      i64 dif = (rr-ll)-cnt;
      cnt = rr-ll;
      return dif;
    }
    if(left == nullptr) {
      assert(right == nullptr);
      i64 m = (ll+rr)/2;
      left = new SegNode {ll, m};
      right = new SegNode {m, rr};
    }
    i64 dl = left->update(l, r);
    i64 dr = right->update(l, r);
//    cout << "retrieved dif " << dl+dr << endl;
    cnt += dl + dr;
    return dl+dr;
  }
  
  i64 query(i64 l, i64 r) {
//    cerr << "querying... " << l << " " << r << endl;
    if(ll>=r || rr <= l) {
      return 0;
    }
    if(l<=ll && r>=rr) {
        return cnt;  
    }
    if(rr-ll == cnt) {
      i64 al = max(ll, l);
      i64 br = min(rr, r);
      
      return br-al;
    }
    
    if(left != nullptr) {
      assert(right != nullptr);
      
      i64 ccnt = left->query(l, r) + right->query(l, r);
//      cout << "retrieved cnt " << ccnt << endl;
      return ccnt;
    }
    
    return 0;
  }
};



SegNode root;

void solve() {
    i64 m;
    cin >> m;
    
    i64 c = 0;
    
    while(m--) {
      i64 d,x,y; cin >> d >> x >> y; x--;
      x+=c;
      y+=c;
      
      if(d==1) {
        i64 res = root.query(x, y);
        c += res;
        cout << res << '\n';
      }
      else {
        root.update(x, y);
      }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    i64 t = 1;
//    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-