Submission #740631

#	Time	Username	Problem	Language	Result	Execution time	Memory
740631		asdf412	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	376 ms	198680 KiB

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 / 100