답안 #377611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
377611	2021-03-14T11:36:39 Z	Valera_Grinenko	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	804 ms	262144 KB

apple

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//sparse segment lazyp tree

struct node {
  int sum, lazy, tl, tr, l, r;
  node() : sum(0), lazy(0), l(-1), r(-1) {}
};
const int N = 1e5 + 42;
node st[64 * N];
int cnt = 2;
void push(int node) {
  if(st[node].lazy) {
    st[node].sum = st[node].tr - st[node].tl + 1;
    int tm = (st[node].tl + st[node].tr) / 2;
    if(st[node].l == -1) {
      st[node].l = cnt++;
      st[st[node].l].tl = st[node].tl;
      st[st[node].l].tr = tm;
    }
    if(st[node].r == -1) {
      st[node].r = cnt++;
      st[st[node].r].tl = tm + 1;
      st[st[node].r].tr = st[node].tr;
    }
    st[st[node].l].lazy = st[st[node].r].lazy = 1;
    st[node].lazy = 0;
  }
}
void upd(int node, int l, int r) {
  push(node);
  if(l == st[node].tl && r == st[node].tr) {
    st[node].lazy = 1;
    push(node);
  } else {
    int tm = (st[node].tl + st[node].tr) / 2;
    if(st[node].l == -1) {
      st[node].l = cnt++;
      st[st[node].l].tl = st[node].tl;
      st[st[node].l].tr = tm;
    }
    if(st[node].r == -1) {
      st[node].r = cnt++;
      st[st[node].r].tl = tm + 1;
      st[st[node].r].tr = st[node].tr;
    }
    if(l > tm) upd(st[node].r, l, r);
    else if(r <= tm) upd(st[node].l, l, r);
    else {
      upd(st[node].l, l, tm);
      upd(st[node].r, tm + 1, r);
    }
    push(st[node].l);
    push(st[node].r);
    st[node].sum = st[st[node].l].sum + st[st[node].r].sum;
  }
}
int query(int node, int l, int r) {
  push(node);
  if(l == st[node].tl && r == st[node].tr) return st[node].sum;
  else {
    int tm = (st[node].tl + st[node].tr) / 2;
    if(st[node].l == -1) {
      st[node].l = cnt++;
      st[st[node].l].tl = st[node].tl;
      st[st[node].l].tr = tm;
    }
    if(st[node].r == -1) {
      st[node].r = cnt++;
      st[st[node].r].tl = tm + 1;
      st[st[node].r].tr = st[node].tr;
    }
    if(l > tm) return query(st[node].r, l, r);
    else if(r <= tm) return query(st[node].l, l, r);
    else return query(st[node].l, l, tm) + query(st[node].r, tm + 1, r);
  }
}
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int m = 0;

  cin >> m;

  st[1].sum = 1;
  st[1].lazy = 0;
  st[1].tl = 1;
  st[1].tr = 1e9 + 42;

  int c = 0;

  while(m--) {
    int d, x, y;
    cin >> d >> x >> y;
    if(d == 2) upd(1, x + c, y + c);
    else {
      int ans = query(1, x + c, y + c);
      c = ans;
      cout << ans << '\n';
    }
  }

  return 0;
}
/*

*/

Compilation message

apple.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	150636 KB	Output is correct
2	Correct	84 ms	150636 KB	Output is correct
3	Correct	95 ms	150636 KB	Output is correct
4	Correct	98 ms	151020 KB	Output is correct
5	Correct	100 ms	150892 KB	Output is correct
6	Correct	102 ms	151020 KB	Output is correct
7	Correct	105 ms	151052 KB	Output is correct
8	Correct	215 ms	151712 KB	Output is correct
9	Correct	376 ms	152940 KB	Output is correct
10	Correct	377 ms	152812 KB	Output is correct
11	Correct	385 ms	153200 KB	Output is correct
12	Correct	385 ms	152864 KB	Output is correct
13	Correct	342 ms	153324 KB	Output is correct
14	Correct	343 ms	153324 KB	Output is correct
15	Runtime error	804 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-