oj.uz

답안 #148145

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148145 2019-08-31T14:49:25 Z catalystgma 원숭이와 사과 나무 (IZhO12_apple) C++11
100 / 100
 840 ms 233076 KB 
#include <bits/stdc++.h>
#define lll long long
#define ldb long double
#define pii pair<int,int>
#define pll pair<lll,lll>
#define pil pair<int,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define maxv 1000000000

using namespace std;

struct nod {
  int ind, lson, rson, val, lazy;
  pii itv;
};

vector <nod> aint;
int ans;

void putlazy (int p) {
  if (aint[p].val == aint[p].itv.se - aint[p].itv.fi + 1) return;
  aint[p].lazy = 1;
}

void mkson (int p) {
  pii it = aint[p].itv; int na, mid = (it.fi + it.se) / 2;
  if (aint[p].lson == 0 && it.fi < it.se) {
    na = sz(aint); aint[p].lson = na;
    aint.pb({na, 0, 0, 0, 0, {it.fi, mid}});
  }
  if (aint[p].rson == 0 && it.fi < it.se) {
    na = sz(aint); aint[p].rson = na;
    aint.pb({na, 0, 0, 0, 0, {mid+1, it.se}});
  }
}

void update (int p, pii ok) {
  pii it = aint[p].itv;
  mkson (p);
  if (aint[p].lazy == 1) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
    aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
  }
  if (it.fi > ok.se || ok.fi > it.se) return;
  if (it.fi >= ok.fi && it.se <= ok.se) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);///!!!
    aint[p].val = it.se - it.fi + 1;
    return;
  }
  if (it.fi == it.se) return;
  update (aint[p].lson, ok);
  update (aint[p].rson, ok);
  aint[p].val = aint[aint[p].lson].val + aint[aint[p].rson].val;
}

int q;
void query (int p, pii ok) {
  pii it = aint[p].itv;
  mkson (p);
  if (aint[p].lazy == 1) {
    if (it.fi < it.se) putlazy(aint[p].lson), putlazy(aint[p].rson);
    aint[p].lazy = 0; aint[p].val = it.se - it.fi + 1;
  }
  if (it.fi > ok.se || ok.fi > it.se) return;
  if (it.fi >= ok.fi && it.se <= ok.se) { q += aint[p].val; return; }
  if (it.fi == it.se) return;
  query (aint[p].lson, ok);
  query (aint[p].rson, ok);
}

int prequery (pii ok) {
  q = 0;
  query (1, ok);
  return q;
}

int main () {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int t; cin >> t;
  aint.pb(nod());
  aint.pb({1,0,0,0,0,{1,maxv}});
  int a, b, op;
  while (t--) {
    cin >> op >> a >> b;
    if (op == 1) {
      ans = prequery ({a+ans,b+ans});
      cout << ans << '\n';
    }
    else update (1, {a+ans, b+ans});
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 30 ms 7776 KB Output is correct
5 Correct 39 ms 7904 KB Output is correct
6 Correct 34 ms 7892 KB Output is correct
7 Correct 38 ms 7908 KB Output is correct
8 Correct 246 ms 58680 KB Output is correct
9 Correct 501 ms 117224 KB Output is correct
10 Correct 512 ms 117100 KB Output is correct
11 Correct 530 ms 116820 KB Output is correct
12 Correct 535 ms 116720 KB Output is correct
13 Correct 611 ms 232988 KB Output is correct
14 Correct 621 ms 233076 KB Output is correct
15 Correct 829 ms 232056 KB Output is correct
16 Correct 827 ms 231904 KB Output is correct
17 Correct 627 ms 233076 KB Output is correct
18 Correct 621 ms 232960 KB Output is correct
19 Correct 834 ms 231980 KB Output is correct
20 Correct 840 ms 231940 KB Output is correct