Submission #1214638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214638		wckiipi	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	314 ms	213480 KiB

apple

// #include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define MAX_INT 2147483647
// #define INT_MIN -2147483648
bool CHECK_FOR_TESTCASE = false;
bool CHECK_NOW = false;
bool FIRST_TESTCASE = true;

using namespace std;
// For tree, uncomment below
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
template <typename T>
using Tree =
    __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag,
                     __gnu_pbds::tree_order_statistics_node_update>;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}

template <typename T> void __print(stack<T> s) {
  vector<T> elements;
  while (!s.empty()) {
    elements.push_back(s.top());
    s.pop();
  }
  reverse(elements.begin(), elements.end());
  __print(elements);
}

template <typename T> void __print(queue<T> q) {
  vector<T> elements;
  while (!q.empty()) {
    elements.push_back(q.front());
    q.pop();
  }
  __print(elements);
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifdef LOCAL_PROJECT
#define debug(x...)                                                            \
  cerr << "[" << #x << "] = [";                                                \
  _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef unsigned long long ull;

ll exp(ll a, ll b, ll mod) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

int N = 5e5 + 5;
vector<ll> fact(N + 1, 1);
vector<ll> inv(N + 1, 1);
ll mod = 998244353;
#define MOD 1000000007

ll ncr(int n, int r) {
  if (r > n) {
    return 0;
  }
  return fact[n] * inv[r] % mod * inv[n - r] % mod;
}

int add(int a, int b) {
  if ((a += b) >= mod)
    a -= mod;

  return a;
}

class DisjointSets {

private:
  vector<int> parents;
  vector<int> sizes;

public:
  DisjointSets(int size) : parents(size), sizes(size, 1) {

    for (int i = 0; i < size; i++) {
      parents[i] = i;
    }
  }

  /** @return the "representative" node in x's component */

  int find(int x) {
    return parents[x] == x ? x : (parents[x] = find(parents[x]));
  }

  /** @return whether the merge changed connectivity */

  bool unite(int x, int y) {
    int x_root = find(x);

    int y_root = find(y);

    if (x_root == y_root) {
      return false;
    }

    if (sizes[x_root] < sizes[y_root]) {
      swap(x_root, y_root);
    }

    sizes[x_root] += sizes[y_root];

    parents[y_root] = x_root;

    return true;
  }

  /** @return whether x and y are in the same connected component */

  bool connected(int x, int y) { return find(x) == find(y); }

  int getSize(int x) { return sizes[find(x)]; }

  int getNumComponents() {
    int count = 0;
    for (int i = 0; i < (int)parents.size(); i++) {
      if (parents[i] == i) {
        count++;
      }
    }
    return count;
  }
};
//
// int mul(int a, int b) { return int(1LL * a * b % MOD); }

// int n = 700, m = 700;

// const ll MOD = 998244353;

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // SplitMix64 hashing algorithm
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

struct STree {
private:
  int n;
  vector<int> a;
  void update(int node, int nodeMin, int nodeMax, int queryLeft, int queryRight,
              int x) {
    if (nodeMin >= queryLeft && nodeMax <= queryRight) {
      a[node] = x;
      return;
    }
    if (nodeMin > queryRight || nodeMax < queryLeft) {
      return;
    }
    int mid = nodeMin + (nodeMax - nodeMin) / 2;
    update(node * 2, nodeMin, mid, queryLeft, queryRight, x);
    update(node * 2 + 1, mid + 1, nodeMax, queryLeft, queryRight, x);

    a[node] = a[node * 2] + a[node * 2 + 1];
  }

  int query(int node, int nodeMin, int nodeMax, int queryLeft, int queryRight) {
    if (nodeMin >= queryLeft && nodeMax <= queryRight) {
      return a[node];
    }
    if (nodeMin > queryRight || nodeMax < queryLeft) {
      return 0;
    }

    int mid = nodeMin + (nodeMax - nodeMin) / 2;
    int left = query(node * 2, nodeMin, mid, queryLeft, queryRight);
    int right = query(node * 2 + 1, mid + 1, nodeMax, queryLeft, queryRight);

    return left + right;
  };

public:
  STree(int _n) : n(_n) { a.resize(4 * _n, 0); };

  void up(int pos, int x) { update(1, 0, n - 1, pos, pos, x); }
  void add(int pos, int x) {
    int val = query(1, 0, n - 1, pos, pos);
    update(1, 0, n - 1, pos, pos, val + x);
  }

  int q(int queryLeft, int queryRight) {
    return query(1, 0, n - 1, queryLeft, queryRight);
  }
};

struct SegTree {
private:
  vector<ll> a;
  vector<ll> lazy;
  ll DEFAULT = 0;
  int n;

  void push(int node, int nodeMin, int nodeMax) {
    if (lazy[node] == 0) {
      return;
    }
    if (nodeMin != nodeMax) {
      int nodeMid = (nodeMin + nodeMax) / 2;

      ll left_size = nodeMid - nodeMin + 1;
      ll right_size = nodeMax - nodeMid;
      if (lazy[node] >= 0) {
        a[node * 2] += (left_size * lazy[node]);
        a[node * 2 + 1] += (right_size * lazy[node]);
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
      } else {
        a[node * 2] = (left_size * -lazy[node]);
        a[node * 2 + 1] = (right_size * -lazy[node]);
        lazy[node * 2] = lazy[node];
        lazy[node * 2 + 1] = lazy[node];
      }
    }
    lazy[node] = 0;
  }

  void update(int node, int nodeMinimum, int nodeMaximum, int queryLow,
              int queryHigh, ll value) {
    int nodeMiddle = (nodeMinimum + nodeMaximum) / 2;

    ll left_size = nodeMiddle - nodeMinimum + 1;
    ll right_size = nodeMaximum - nodeMiddle;
    if (nodeMinimum >= queryLow && nodeMaximum <= queryHigh) {
      a[node] += (value * (ll)(nodeMaximum - nodeMinimum + 1));
      lazy[node] += value;
      return;
    }
    if (nodeMaximum < queryLow || nodeMinimum > queryHigh) {
      return;
    }

    push(node, nodeMinimum, nodeMaximum);
    update(node * 2, nodeMinimum, nodeMiddle, queryLow, queryHigh, value);
    update(node * 2 + 1, nodeMiddle + 1, nodeMaximum, queryLow, queryHigh,
           value);
    // a[node] = min(a[node * 2], a[node * 2 + 1]);
    a[node] = a[node * 2] + a[node * 2 + 1];
  }
  void updateValue(int node, int nodeMinimum, int nodeMaximum, int queryLow,
                   int queryHigh, ll value) {
    int nodeMiddle = (nodeMinimum + nodeMaximum) / 2;

    ll left_size = nodeMiddle - nodeMinimum + 1;
    ll right_size = nodeMaximum - nodeMiddle;
    if (nodeMinimum >= queryLow && nodeMaximum <= queryHigh) {
      // a[node] = (value * (ll)(nodeMaximum - nodeMinimum + 1));
      a[node] = (value * (ll)(nodeMaximum - nodeMinimum + 1));
      lazy[node] = -value;
      // lazy[node] += value;
      return;
    }
    if (nodeMaximum < queryLow || nodeMinimum > queryHigh) {
      return;
    }

    push(node, nodeMinimum, nodeMaximum);
    update(node * 2, nodeMinimum, nodeMiddle, queryLow, queryHigh, value);
    update(node * 2 + 1, nodeMiddle + 1, nodeMaximum, queryLow, queryHigh,
           value);
    // a[node] = min(a[node * 2], a[node * 2 + 1]);
    a[node] = a[node * 2] + a[node * 2 + 1];
  }

  ll query(int node, int nodeMinimum, int nodeMaximum, int queryLow,
           int queryHigh) {
    if (nodeMinimum >= queryLow && nodeMaximum <= queryHigh) {
      return a[node];
    }
    if (nodeMaximum < queryLow || nodeMinimum > queryHigh) {
      return 0;
    }

    int nodeMiddle = (nodeMinimum + nodeMaximum) / 2;
    push(node, nodeMinimum, nodeMaximum);
    ll solution =
        query(node * 2, nodeMinimum, nodeMiddle, queryLow, queryHigh) +
        query(node * 2 + 1, nodeMiddle + 1, nodeMaximum, queryLow, queryHigh);

    return solution;
  }

public:
  SegTree(int _n) : n(_n) {
    a.resize(4 * _n, DEFAULT);
    lazy.resize(4 * _n, 0);
  }
  void updateVal(int l, int r, ll x) { updateValue(1, 0, n - 1, l, r, x); }
  void updateRange(int l, int r, ll x) { update(1, 0, n - 1, l, r, x); }
  ll que(int l, int r) { return query(1, 0, n - 1, l, r); }
  // int find(int l, int r, int k) {
  //   if (l == r) {
  //     if (que(l, r) < k) {
  //       return INT_MIN;
  //     } else {
  //       return l;
  //     }
  //   }
  //   int mid = l + (r - l) / 2;
  //   int maxL = que(l, mid);
  //   if (maxL >= k) {
  //     return find(l, mid, k);
  //   } else {
  //     return find(mid + 1, r, k);
  //   }
  // }
};

struct sparseSegment {

public:
  struct Node {
    Node *l, *r;
    ll a;
    Node(ll _a) : l(nullptr), r(nullptr), a(_a) {}
  };
  sparseSegment(int _n) : n(_n) { root = new Node(DEFAULT); }

  int n;
  ll DEFAULT = 0;
  Node *root;

  ll query(Node *node, int nodeMin, int nodeMax, int queryLow, int queryHigh) {
    int nodeMid = (nodeMin + nodeMax) / 2;
    if (node == nullptr) {
      return DEFAULT;
    }
    if (nodeMin >= queryLow && nodeMax <= queryHigh) {
      return node->a;
    }
    if (nodeMax < queryLow || nodeMin > queryHigh) {
      return DEFAULT;
    }

    ll left = query(node->l, nodeMin, nodeMid, queryLow, queryHigh);
    ll right = query(node->r, nodeMid + 1, nodeMax, queryLow, queryHigh);
    return left + right;
  }

  void update(Node *&node, int nodeMin, int nodeMax, int queryLow,
              int queryHigh, ll x) {
    if (node == nullptr) {
      node = new Node(0);
    }
    if (nodeMin >= queryLow && nodeMax <= queryHigh) {
      node->a = x;
      return;
    }
    if (nodeMax < queryLow || nodeMin > queryHigh) {
      return;
    }
    int nodeMid = (nodeMin + nodeMax) / 2;
    update(node->l, nodeMin, nodeMid, queryLow, queryHigh, x);
    update(node->r, nodeMid + 1, nodeMax, queryLow, queryHigh, x);
    ll left = node->l ? node->l->a : DEFAULT;
    ll right = node->r ? node->r->a : DEFAULT;
    node->a = left + right;
  }
};

struct LazySparseSegmentTree {
  int n;
  struct Node {
    ll a = 0;
    Node *l, *r;
    ll lazy = -1;
    Node(ll _a) : a(_a), l(nullptr), r(nullptr) {}
  };
  Node *root = nullptr;

  LazySparseSegmentTree(int _n) : n(_n) { root = new Node(0); }

  void push(Node *node, int nodeLow, int nodeHigh) {
    if (node == nullptr || node->lazy == -1) {
      return;
    }
    if (node->l == nullptr) {
      node->l = new Node(0);
    }
    if (node->r == nullptr) {
      node->r = new Node(0);
    }
    int nodeMid = nodeLow + (nodeHigh - nodeLow) / 2;
    int left = nodeMid - nodeLow + 1;
    int right = nodeHigh - nodeMid;

    node->l->a = left * node->lazy;
    node->l->lazy = node->lazy;
    node->r->a = right * node->lazy;
    node->r->lazy = node->lazy;
    node->lazy = -1;
  }

  void update(Node *&node, int nodeLow, int nodeHigh, int queryLow,
              int queryHigh, ll x) {
    if (node == nullptr) {
      node = new Node(0);
    }
    int nodeMid = nodeLow + (nodeHigh - nodeLow) / 2;
    ll size = nodeHigh - nodeLow + 1;

    if (nodeLow >= queryLow && nodeHigh <= queryHigh) {
      node->a = x * size;
      node->lazy = x;
      return;
    }
    if (nodeHigh < queryLow || nodeLow > queryHigh) {
      return;
    }
    push(node, nodeLow, nodeHigh);
    update(node->l, nodeLow, nodeMid, queryLow, queryHigh, x);
    update(node->r, nodeMid + 1, nodeHigh, queryLow, queryHigh, x);
    node->a = 0;
    if (node->l) {
      node->a += node->l->a;
    }
    if (node->r) {
      node->a += node->r->a;
    }
  }

  ll query(Node *node, int nodeLow, int nodeHigh, int queryLow, int queryHigh) {
    if (node == nullptr) {
      return 0;
    }

    if (nodeLow >= queryLow && nodeHigh <= queryHigh) {
      return node->a;
    }
    if (nodeHigh < queryLow || nodeLow > queryHigh) {
      return 0;
    }
    int nodeMid = nodeLow + (nodeHigh - nodeLow) / 2;
    push(node, nodeLow, nodeHigh);
    ll left = query(node->l, nodeLow, nodeMid, queryLow, queryHigh);
    ll right = query(node->r, nodeMid + 1, nodeHigh, queryLow, queryHigh);
    return left + right;
  }
};

#define HAS_TESTCASE 0

void useOnce() {}

void solve() {
  int n;
  cin >> n;
  ll c = 0;
  LazySparseSegmentTree seg(1e9 + 5);

  for (int i = 0; i < n; i++) {
    ll type, l, r;
    cin >> type >> l >> r;
    --l, r--;
    l += c;
    r += c;
    if (type == 1) {
      c = seg.query(seg.root, 0, 1e9, l, r);
      cout << c << "\n";
    } else {
      seg.update(seg.root, 0, 1e9, l, r, 1);
    }
  }
}

int main() {
  useOnce();
  cin.tie(0)->sync_with_stdio(false);
#ifdef LOCAL_PROJECT
  freopen("error.txt", "w", stderr);
#endif
  // freopen("boards.in", "r", stdin); freopen("boards.out", "w", stdout);

  if (HAS_TESTCASE) {
    int t;
    cin >> t;
    int T = t;
    while (t--) {
      // if (t != T - 1) {
      //   FIRST_TESTCASE = false;
      // }
      // if (t == (10000 - 1722)) {
      //   CHECK_NOW = true;
      // } else {
      //   CHECK_NOW = false;
      // }
      // solve_bruteforce();
      solve();
    }
  } else {
    solve();
  }
}

• Subtask 1: 100 / 100