Submission #740627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
740627	2023-05-12T21:51:55 Z	asdf412	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1 ms	340 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;

struct Node
{
  int id;
  ll val, lazy, idl, idr;

  Node(int v, int i, int l, int r)
  {
    val = v;
    id = i;
    idl = l;
    idr = r;
    lazy = 0;
  };
};

vector<Node> seg;

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

void extend(int idx)
{
  if (seg[idx].idl == -1)
  {
    seg[idx].idl = seg.size();
    seg.push_back(Node(0, seg.size(), -1, -1));
  }
  if (seg[idx].idr == -1)
  {
    seg[idx].idr = seg.size();
    seg.push_back(Node(0, seg.size(), -1, -1));
  }
}

void upd(ll ql, ll qr, ll v, int idx = 0, ll l = 0, ll r = n)
{
  //cout << " w " << v << ' ' << idx << ' ' << l << ' ' << r << '\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;
    if (l != r)
    {
      seg[tl].lazy += v;
      seg[tr].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 << '\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);
  seg.push_back(Node(0, 0, -1, -1));

  cin >> m;

  // Node A(5, 0, -1, -1);

  // cout << A.id << ' ' << A.val;

  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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-