Submission #740631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
740631	2023-05-12T22:25:46 Z	asdf412	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	376 ms	198680 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[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

#	Verdict	Execution time	Memory	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