Submission #919845

#TimeUsernameProblemLanguageResultExecution timeMemory
919845NeltMonkey and Apple-trees (IZhO12_apple)C++17
100 / 100
234 ms170320 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* DEFINES */ #define S second #define F first #define ll long long #define ull unsigned long long #define ld long double #define npos ULLONG_MAX #define INF LLONG_MAX #define vv(a) vector<a> #define ss(a) set<a> #define pp(a, b) pair<a, b> #define mm(a, b) map<a, b> #define qq(a) queue<a> #define pq(a) priority_queue<a> #define ump(a, b) unordered_map<a, b> #define ANDROID \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define allc(a) begin(a), end(a) #define all(a) a, a + sizeof(a) / sizeof(a[0]) #define elif else if #define endl "\n" #define pb push_back #define ins insert #define logi __lg #define sqrt sqrtl #define mpr make_pair using namespace std; using namespace __cxx11; using namespace __gnu_pbds; typedef char chr; typedef basic_string<chr> str; template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 1e5 + 5; ll L[N * 60], R[N * 60], st[N * 60], lazy[N * 60], ptr = 2; void push(ll v, ll l, ll r) { if (!lazy[v]) return; lazy[v] = 0; ll mid = (l + r) >> 1; if (L[v] == -1) L[v] = ptr++; if (R[v] == -1) R[v] = ptr++; st[L[v]] = mid - l + 1, lazy[L[v]] = 1; st[R[v]] = r - mid, lazy[R[v]] = 1; } ll query(ll i, ll j, ll l, ll r, ll v) { if (v == -1) return 0; if (i <= l and r <= j) return st[v]; ll mid = (l + r) >> 1; push(v, l, r); if (j <= mid) return query(i, j, l, mid, L[v]); if (i > mid) return query(i, j, mid + 1, r, R[v]); return query(i, j, l, mid, L[v]) + query(i, j, mid + 1, r, R[v]); } ll modify(ll i, ll j, ll l, ll r, ll v) { if (v == -1) v = ptr++; if (max(i, l) > min(j, r)) return v; if (i <= l and r <= j) { st[v] = r - l + 1; lazy[v] = 1; return v; } push(v, l, r); ll mid = (l + r) >> 1; L[v] = modify(i, j, l, mid, L[v]); R[v] = modify(i, j, mid + 1, r, R[v]); st[v] = st[L[v]] + st[R[v]]; return v; } void solve() { ll q; cin >> q; for (ll i = 1; i < 60 * N; i++) L[i] = R[i] = -1; ll c = 0; while (q--) { ll t, l, r; cin >> t >> l >> r; l += c, r += c; if (t == 2) modify(l, r, 1, 1e9, 1); else cout << (c = query(l, r, 1, 1e9, 1)) << endl; } } /* */ int main() { ANDROID // precomp(); ll t = 1; // cin >> t; for (ll i = 1; i <= t; i++) // cout << "Case #" << i << ": ", solve(); cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...