Submission #1143468

#TimeUsernameProblemLanguageResultExecution timeMemory
1143468ammahmed004Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
357 ms327680 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) #define ll long long #define ld long double #define int long long #define endl "\n" #define yes cout<<"YES"<<endl; #define no cout<<"NO"<<endl; #define pb push_back //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; const int MOD = 1e9 + 7; //const int MOD = 998244353 ; const int N = 4e5 + 5; const ll INF = 1e18; const ll MIN = -1e18; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; int Tree[30 * N]; int l_child[30 * N]; int r_child[30 * N]; int lazy[30 * N]; int upd[30 * N]; int cnt; int get_val(int id) { if (id == -1)return 0; return Tree[id]; } int creat() { Tree[cnt] = 0; lazy[cnt] = 0; upd[cnt] = 0; l_child[cnt] = r_child[cnt] = -1; return cnt++; } void unlazy(int id, int ns, int ne) { if (id == -1)return; if (upd[id] == 0) return; if (l_child[id] == -1) { l_child[id] = creat(); } if (r_child[id] == -1) { r_child[id] = creat(); } Tree[id] = (ne - ns + 1); lazy[l_child[id]] = lazy[r_child[id]] = lazy[id]; upd[id] = 0; upd[r_child[id]] = upd[l_child[id]] = 1; } int query(int qs, int qe, int ns = 1, int ne = 1e9+5, int id = 0) { if (id == -1)return 0; unlazy(id, ns, ne); if (ne < qs || ns > qe) return 0; if (qs <= ns && ne <= qe) return Tree[id]; int idl = l_child[id], idr = r_child[id], md = ns + (ne - ns) / 2; int one = query(qs, qe, ns, md, idl); int two = query(qs, qe, md + 1, ne, idr); return one + two; } int update(int qs, int qe, int val, int ns = 1, int ne = 1e9+5, int id = 0) { unlazy(id, ns, ne); if (qs > ne || qe < ns) return id; if (id == -1)id = creat(); if (qs <= ns && ne <= qe) { lazy[id] = val; upd[id] = 1; unlazy(id, ns, ne); return id; } int md = ns + (ne - ns) / 2; int idl = l_child[id]; int idr = r_child[id]; l_child[id] = update(qs, qe, val, ns, md, idl); r_child[id] = update(qs, qe, val, md + 1, ne, idr); Tree[id] = get_val(l_child[id]) + get_val(r_child[id]); return id; } void solve() { cnt = 0; creat(); ll c = 0; ll q;cin >> q; while (q--) { ll d, x, y; cin >> d >> x >> y; if (d == 1) { c = query(x + c, y + c); cout << c << endl; } else { update(x + c, y + c, 1); } } } signed main() { FAST; ll t = 1; //cin>>t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...