답안 #740630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
740630	2023-05-12T22:23:15 Z	asdf412	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	379 ms	262144 KB

apple

#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[7000000];

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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	137160 KB	Output is correct
2	Correct	62 ms	137296 KB	Output is correct
3	Correct	64 ms	137192 KB	Output is correct
4	Correct	75 ms	137420 KB	Output is correct
5	Correct	71 ms	137264 KB	Output is correct
6	Correct	70 ms	137224 KB	Output is correct
7	Correct	74 ms	137216 KB	Output is correct
8	Correct	156 ms	137420 KB	Output is correct
9	Correct	267 ms	137656 KB	Output is correct
10	Correct	271 ms	137672 KB	Output is correct
11	Correct	283 ms	137700 KB	Output is correct
12	Correct	287 ms	137740 KB	Output is correct
13	Correct	261 ms	139892 KB	Output is correct
14	Correct	258 ms	139776 KB	Output is correct
15	Runtime error	379 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-