제출 #745663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745663		asdf412	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	522 ms	262144 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 val = 0, lazy = 0;
  Node *l = NULL, *r = NULL;
 
  Node() {}
 
};
 
Node *seg;
 
void push(ll l, ll r, Node *tn)
{
  if (tn->lazy) {
    ll mi = (l + r) >> 1;
    tn->val = (r - l + 1) * tn->lazy;
    tn->l->lazy = tn->lazy;
    tn->r->lazy = tn->lazy;
    tn->l->val = (mi - l + 1) * tn->lazy;
    tn->r->val = (r - mi) * tn->lazy;
  }
  tn->lazy = 0;
}
 
 
void upd(ll ql, ll qr, ll v, Node *tn, ll l = 0, ll r = n)
{
  //cout << " w " << v << ' ' << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  ll mi = (l + r) >> 1;
  if (tn->l == NULL) {
    tn->l = new Node();
  }
  if (tn->r == NULL) {
    tn->r = new Node();
  }
  push(l, r, tn);

  if (l > qr || r < ql)
    return;
  if (ql <= l && qr >= r) {
    tn->val = (r - l + 1) * v;
    tn->lazy = v;
    return;
  }

  upd(ql, qr, v, tn->l, l, mi);
  upd(ql, qr, v, tn->r, mi + 1, r);
  tn->val = tn->l->val + tn->r->val;
}
 
ll qur(ll ql, ll qr, Node *tn, ll l = 0, ll r = n)
{
  //cout << " wq " << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  ll mi = (l + r) >> 1;
  if (tn->l == NULL) {
    tn->l = new Node();
  }
  if (tn->r == NULL) {
    tn->r = new Node();
  }  
  push(l, r, tn);
  
  if (l > qr || r < ql || tn == NULL)
    return 0;
  if (ql <= l && qr >= r)
    return tn->val;

  return qur(ql, qr, tn->l, l, mi) + qur(ql, qr, tn->r, mi + 1, r);
}
ll c = 0;
 
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  cin >> m;

  seg = new Node();
 
  while (m--)
  {
    int x;
    cin >> x;
    if (x == 2)
    {
      ll a, b;
      cin >> a >> b;
      upd(a + c, b + c, 1, seg);
      //qur(a + c, b + c);
    }
    else
    {
      ll a, b;
      cin >> a >> b;
      c = qur(a + c, b + c, seg);
      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