Submission #745663

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745663	2023-05-20T20:01:00 Z	asdf412	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	522 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 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	6316 KB	Output is correct
5	Correct	22 ms	7620 KB	Output is correct
6	Correct	20 ms	7392 KB	Output is correct
7	Correct	20 ms	7700 KB	Output is correct
8	Correct	152 ms	57948 KB	Output is correct
9	Correct	321 ms	100684 KB	Output is correct
10	Correct	327 ms	111248 KB	Output is correct
11	Correct	323 ms	119628 KB	Output is correct
12	Correct	335 ms	123300 KB	Output is correct
13	Correct	340 ms	143640 KB	Output is correct
14	Correct	300 ms	145036 KB	Output is correct
15	Runtime error	522 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-