oj.uz

답안 #737673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737673 2023-05-07T14:03:39 Z cig32 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 245 ms 173660 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 9 ms 4180 KB Output is correct
5 Correct 11 ms 5076 KB Output is correct
6 Correct 11 ms 4948 KB Output is correct
7 Correct 11 ms 5076 KB Output is correct
8 Correct 82 ms 37412 KB Output is correct
9 Correct 185 ms 64844 KB Output is correct
10 Correct 173 ms 71564 KB Output is correct
11 Correct 182 ms 76744 KB Output is correct
12 Correct 195 ms 79276 KB Output is correct
13 Correct 158 ms 92108 KB Output is correct
14 Correct 159 ms 93004 KB Output is correct
15 Correct 245 ms 168580 KB Output is correct
16 Correct 240 ms 169836 KB Output is correct
17 Correct 165 ms 96076 KB Output is correct
18 Correct 167 ms 96152 KB Output is correct
19 Correct 240 ms 173616 KB Output is correct
20 Correct 234 ms 173660 KB Output is correct