oj.uz

답안 #740631

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
740631 2023-05-12T22:25:46 Z asdf412 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 376 ms 198680 KB 
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define tp tuple<ll, ll, ll>
#define F first
#define S second
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define eb emplace_back

using namespace std;
const int n = 1e9;
int m, curr = 1;

struct Node
{
  int id;
  int val = 0, lazy = 0, idl = -1, idr = -1;

  Node() : id(0) {}

};

Node seg[10000000];

void push(ll l, ll r, ll idx)
{
  if (seg[idx].lazy) {
    ll mi = (l + r) >> 1;
    int il = seg[idx].idl, ir = seg[idx].idr;
    seg[idx].val = (r - l + 1) * seg[idx].lazy;
    seg[il].lazy = seg[idx].lazy;
    seg[ir].lazy = seg[idx].lazy;
    seg[il].val = (mi - l + 1) * seg[idx].lazy;
    seg[ir].val = (r - mi) * seg[idx].lazy;
  }
  seg[idx].lazy = 0;
}

void extend(int idx)
{
  if (seg[idx].idl == -1)
  {
    seg[idx].idl = curr++;
  }
  if (seg[idx].idr == -1)
  {
    seg[idx].idr = curr++;
  }
}

void upd(ll ql, ll qr, ll v, int idx = 0, ll l = 0, ll r = n)
{
  //cout << " w " << v << ' ' << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  extend(idx);
  push(l, r, idx);
  ll mi = (l + r) >> 1;
  int tl = seg[idx].idl, tr = seg[idx].idr;
  if (l > qr || r < ql)
    return;
  if (ql <= l && qr >= r)
  {
    seg[idx].val = (r - l + 1) * v;
    seg[idx].lazy = v;
    return;
  }
  
  upd(ql, qr, v, tl, l, mi);
  upd(ql, qr, v, tr, mi + 1, r);
  seg[idx].val = seg[tl].val + seg[tr].val;
}

ll qur(ll ql, ll qr, int idx = 0, ll l = 0, ll r = n)
{
  //cout << " wq " << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  extend(idx);
  push(l, r, idx);
  ll mi = (l + r) >> 1;
  int tl = seg[idx].idl, tr = seg[idx].idr;
  if (l > qr || r < ql)
    return 0;
  if (ql <= l && qr >= r)
    return seg[idx].val;
  return qur(ql, qr, tl, l, mi) + qur(ql, qr, tr, mi + 1, r);
}
ll c = 0;

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

  cin >> m;

  while (m--)
  {
    int x;
    cin >> x;
    if (x == 2)
    {
      ll a, b;
      cin >> a >> b;
      upd(a + c, b + c, 1);
      //qur(a + c, b + c);
    }
    else
    {
      ll a, b;
      cin >> a >> b;
      c = qur(a + c, b + c);
      cout << c << '\n';
    }

    //for (int i = 0; i < 20; ++i)cout << qur(i, i) << ' ';
    //cout << '\n';
    // cout << seg.size() << '\n';
  }
  //for (int i = 0; i < 20; ++i)cout << qur(i, i) << ' ';
    //cout << '\n';

  return 0;
}
/*
6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17

3
2 5 8
2 7 10
1 1 10

*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 195968 KB Output is correct
2 Correct 87 ms 196128 KB Output is correct
3 Correct 82 ms 195872 KB Output is correct
4 Correct 104 ms 195920 KB Output is correct
5 Correct 101 ms 195912 KB Output is correct
6 Correct 96 ms 195972 KB Output is correct
7 Correct 100 ms 196044 KB Output is correct
8 Correct 210 ms 196096 KB Output is correct
9 Correct 297 ms 196268 KB Output is correct
10 Correct 332 ms 196380 KB Output is correct
11 Correct 307 ms 196364 KB Output is correct
12 Correct 340 ms 196384 KB Output is correct
13 Correct 282 ms 196396 KB Output is correct
14 Correct 323 ms 196356 KB Output is correct
15 Correct 359 ms 198652 KB Output is correct
16 Correct 363 ms 198656 KB Output is correct
17 Correct 292 ms 198444 KB Output is correct
18 Correct 302 ms 198540 KB Output is correct
19 Correct 354 ms 198580 KB Output is correct
20 Correct 376 ms 198680 KB Output is correct