oj.uz

답안 #377615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377615 2021-03-14T11:38:41 Z Valera_Grinenko 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 479 ms 188652 KB 
#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 = 123456;
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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 185836 KB Output is correct
2 Correct 108 ms 185964 KB Output is correct
3 Correct 107 ms 185940 KB Output is correct
4 Correct 121 ms 186000 KB Output is correct
5 Correct 124 ms 186092 KB Output is correct
6 Correct 121 ms 186092 KB Output is correct
7 Correct 124 ms 186092 KB Output is correct
8 Correct 236 ms 186476 KB Output is correct
9 Correct 399 ms 186732 KB Output is correct
10 Correct 406 ms 186348 KB Output is correct
11 Correct 402 ms 186860 KB Output is correct
12 Correct 421 ms 186860 KB Output is correct
13 Correct 352 ms 186960 KB Output is correct
14 Correct 365 ms 186956 KB Output is correct
15 Correct 474 ms 188524 KB Output is correct
16 Correct 473 ms 188652 KB Output is correct
17 Correct 362 ms 188524 KB Output is correct
18 Correct 368 ms 188652 KB Output is correct
19 Correct 479 ms 188652 KB Output is correct
20 Correct 479 ms 188560 KB Output is correct