Submission #745662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745662	2023-05-20T19:54:22 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, lo = 0, hi = 0;
  Node *l = NULL, *r = NULL;
 
  Node(int a, int b) : lo(a), hi(b) {}
 
};
 
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)
{
  //cout << " w " << v << ' ' << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  ll l = tn->lo, r = tn->hi;
  ll mi = (l + r) >> 1;
  if (tn->l == NULL) {
    tn->l = new Node(l, mi);
  }
  if (tn->r == NULL) {
    tn->r = new Node(mi + 1, r);
  }
  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);
  upd(ql, qr, v, tn->r);
  tn->val = tn->l->val + tn->r->val;
}
 
ll qur(ll ql, ll qr, Node *tn)
{
  //cout << " wq " << idx << ' ' << l << ' ' << r << ' ' << curr << '\n';
  ll l = tn->lo, r = tn->hi;
  ll mi = (l + r) >> 1;
  if (tn->l == NULL) {
    tn->l = new Node(l, mi);
  }
  if (tn->r == NULL) {
    tn->r = new Node(mi + 1, r);
  }  
  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) + qur(ql, qr, tn->r);
}
ll c = 0;
 
int main()
{
  //ios_base::sync_with_stdio(0);
  //cin.tie(0);
 
  cin >> m;

  seg = new Node(0, n);
 
  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	28 ms	9476 KB	Output is correct
5	Correct	34 ms	11460 KB	Output is correct
6	Correct	33 ms	11068 KB	Output is correct
7	Correct	33 ms	11456 KB	Output is correct
8	Correct	237 ms	87776 KB	Output is correct
9	Correct	507 ms	152496 KB	Output is correct
10	Correct	522 ms	168280 KB	Output is correct
11	Correct	514 ms	180832 KB	Output is correct
12	Correct	502 ms	186436 KB	Output is correct
13	Correct	475 ms	217120 KB	Output is correct
14	Correct	489 ms	219324 KB	Output is correct
15	Runtime error	493 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-