Submission #737673

#	Time	Username	Problem	Language	Result	Execution time	Memory
737673		cig32	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	245 ms	173660 KiB

apple

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 1e9 +7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }

struct node {
  int lc = 0, rc = 0, lazy = 0, sum = 0;
  bool have = 0;
} st[10000000];
int unused = 1;
void push_down(int idx, int lc, int rc, int llen, int rlen) {
  if(st[idx].have == 0) return;
  st[lc].have = 1;
  st[lc].lazy = st[idx].lazy;
  st[lc].sum = st[idx].lazy * llen;
  st[rc].have = 1;
  st[rc].lazy = st[idx].lazy;
  st[rc].sum = st[idx].lazy * rlen;
  st[idx].have = 0;
  st[idx].lazy = 0;
}
void push_up(int idx, int lc, int rc) {
  st[idx].sum = st[lc].sum + st[rc].sum;
}
void u(int l, int r, int constl, int constr, int idx, int val) { // range := val
  if(l <= constl && constr <= r) {
    st[idx].have = 1;
    st[idx].lazy = val;
    st[idx].sum = val * (constr - constl + 1); 
    return;
  }
  int mid = (constl + constr) >> 1;
  if(st[idx].lc == 0) st[idx].lc = unused++;
  if(st[idx].rc == 0) st[idx].rc = unused++;
  push_down(idx, st[idx].lc, st[idx].rc, mid - constl + 1, constr - mid);
  if(mid < l || r < constl) u(l, r, mid+1, constr, st[idx].rc, val);
  else if(constr < l || r < mid+1) u(l, r, constl, mid, st[idx].lc, val);
  else {
    u(l, r, constl, mid, st[idx].lc, val);
    u(l, r, mid+1, constr, st[idx].rc, val);
  }
  
  push_up(idx, st[idx].lc, st[idx].rc);
}
int qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) {
    return st[idx].sum;
  }
  int mid = (constl + constr) >> 1;
  if(st[idx].lc == 0) st[idx].lc = unused++;
  if(st[idx].rc == 0) st[idx].rc = unused++;
  push_down(idx, st[idx].lc, st[idx].rc, mid - constl + 1, constr - mid);
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, st[idx].rc);
  else if(constr < l || r < mid+1) return qu(l, r, constl, mid, st[idx].lc);
  else return qu(l, r, constl, mid, st[idx].lc) + qu(l, r, mid+1, constr, st[idx].rc);
}
void solve(int tc) {
  int m;
  cin >> m;
  int c=0;
  for(int i=0; i<m; i++) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c, y += c;
    if(d == 1) {
      c = qu(x, y, 1, 1000000000, 0);
      cout << c << "\n";
    }
    else {
      u(x, y, 1, 1000000000, 0, 1);
    }
  }
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 搏盡

• Subtask 1: 100 / 100