Submission #822985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822985	2023-08-12T06:32:12 Z	arush_agu	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	252 ms	190856 KB

apple

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9 + 5;
const ld EPS = 1e-9;

const int MAX = 2e5 + 5;

struct Node {
  int val, lazy, l, r;
  Node() : val(0), lazy(0), l(-1), r(-1){};
};

struct ST {
  vector<Node> f;
  int n;

  ST() : f(MAX * 60), n(1){};

  void push(int x, int l, int r) {
    if (!f[x].lazy)
      return;
    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;

    int m = (l + r) / 2;
    f[f[x].l].lazy = f[x].lazy;
    f[f[x].r].lazy = f[x].lazy;
    f[f[x].l].val = f[x].lazy * (m - l + 1);
    f[f[x].r].val = f[x].lazy * (r - m);
    f[x].lazy = 0;
  }

  void upd(int u, int v, int val, int x = 1, int l = 1, int r = INF) {
    if (l > v || r < u)
      return;
    if (u <= l && r <= v) {
      f[x].val = val * (r - l + 1);
      f[x].lazy = val;
      return;
    }

    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;
    push(x, l, r);

    int m = (l + r) >> 1;
    upd(u, v, val, f[x].l, l, m);
    upd(u, v, val, f[x].r, m + 1, r);
    f[x].val = f[f[x].l].val + f[f[x].r].val;
  }

  int query(int u, int v, int x = 1, int l = 1, int r = INF) {
    if (l > v || r < u)
      return 0;
    if (u <= l && r <= v)
      return f[x].val;

    if (f[x].l == -1)
      f[x].l = ++n;
    if (f[x].r == -1)
      f[x].r = ++n;
    push(x, l, r);

    int m = (l + r) >> 1;
    int ql = query(u, v, f[x].l, l, m);
    int qr = query(u, v, f[x].r, m + 1, r);
    return (ql + qr);
  }
};

void solve() {
  int q;
  ST st;
  cin >> q;
  int c = 0;
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1)
      cout << (c = st.query(x + c, y + c)) << "\n";
    else
      st.upd(x + c, y + c, 1);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:180:11: warning: unused variable 'start' [-Wunused-variable]
  180 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	78 ms	188080 KB	Output is correct
2	Correct	73 ms	188128 KB	Output is correct
3	Correct	79 ms	188068 KB	Output is correct
4	Correct	79 ms	188188 KB	Output is correct
5	Correct	87 ms	188208 KB	Output is correct
6	Correct	80 ms	188220 KB	Output is correct
7	Correct	82 ms	188160 KB	Output is correct
8	Correct	122 ms	188284 KB	Output is correct
9	Correct	199 ms	188464 KB	Output is correct
10	Correct	229 ms	188568 KB	Output is correct
11	Correct	189 ms	188548 KB	Output is correct
12	Correct	199 ms	188524 KB	Output is correct
13	Correct	184 ms	188620 KB	Output is correct
14	Correct	176 ms	188684 KB	Output is correct
15	Correct	219 ms	189548 KB	Output is correct
16	Correct	252 ms	190856 KB	Output is correct
17	Correct	180 ms	190668 KB	Output is correct
18	Correct	182 ms	190712 KB	Output is correct
19	Correct	230 ms	190848 KB	Output is correct
20	Correct	222 ms	190816 KB	Output is correct