Untitled
unknown
plain_text
a year ago
15 kB
1
Indexable
Never
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include<bits/stdc++.h> #include<unordered_map> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> // for less using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define endl '\n' #define ll long long // #define ll int #define ull unsigned ll #define sz(v) (int)(v.size()) #define ld long double #define pb push_back #define em emplace_back #define ppb pop_back #define all(x) (x).begin(), (x).end() #define sai(a,n) sort(a,a+n); #define sad(a,n) sort(a,a+n,greater<decltype<*a>>()); #define svi(x) sort(x.begin(), x.end()); #define svd(a) sort(a.begin(), a.end(), greater<ll>()); #define FAST ios_base::sync_with_stdio(0);cin.tie(0); #define fi(i,x,n) for (auto i(x); i < n; ++i) #define fr(i,x,n) for (auto i(x-1);i >= n; --i) #define vi vector <ll> #define vvi vector<vi> #define mp(a1,a2) make_pair(a1,a2) #define gll ll static #define rll register ll #define reg register #define pii pair<ll, ll> #define vp vector<pii> #define vs vector<string> #define vb vector<bool> #define vvb vector<vb> #define vvp vector<vp> #define read(a,n) fi(i,0,n){cin>>a[i];} #define read_tree(g,m) fi(i,0,m) {ll u,v;cin>>u>>v;g[u].em(v);g[v].em(u);} #define mii map<ll, ll> #define umii unordered_map<ll, ll> #define msi map<string, ll> #define mss map<string, string> #define pqi priority_queue <ll> #define pqii priority_queue <ll,vi,greater<ll>> #define mci map<char, ll> #define umci unordered_map<char, ll> #define vmax(v) *max_element(all(v)); #define vmin(v) *min_element(all(v)); #define mdsu(s,e) fi(i,s,e+1) make_set(i); #define ret(a) {cout<<a<<endl; return;} #define F first #define S second #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" = "; _print(x); cerr << endl; #else #define debug(x) #endif template<typename T, typename U> static inline void amin(T &x, U&& y){if(y<x) x=y;} template<typename T, typename U> static inline void amax(T &x, U&& y){if(x<y) x=y;} template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i;return v;} template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i;return v;} template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;} template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;} template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;} template<typename T> ostream& operator<<(ostream& os, vector<T> &v){for (auto& i : v) os << i << ' '; return os;} template<typename T> ostream& operator<<(ostream& os, set<T> &v){for (auto& i : v) os << i << ' '; return os;} template<typename T> ostream& operator<<(ostream& os, unordered_set<T> &v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> ostream& operator<<(ostream& os, unordered_map<T,U> &v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> ostream& operator<<(ostream& os, map<T,U> &v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second;return p;} template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second;return p;} template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);} template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);} void _print(ll t) {cerr << t;} template<typename T> static inline void _print(T &&t){cerr << t;} template<typename T> struct Hasher { size_t operator()(const vector<T> &myVector) const { std::hash<T> hasher; size_t answer = 0; for (auto i : myVector) { answer ^= hasher(i) + 0x9e3779b9 + (answer << 6) + (answer >> 2); } return answer; } }; bool kahn(); void bfs(ll source); void grid_dfs(ll i, ll j, vs &s, vvb &vis); void grid_bfs(ll i, ll j, vs &s); void dijkstra(ll source, vp g[], ll n); void primes(); bool prmchk(ll n); ll modi(ll x, ll m); ll binpow(ll a, ll b); ll binpowm(ll a, ll b, ll mod); ll lcm(ll a, ll b); string bin(ll x); vi previousGreaterElement(vi &a, int n); vi preSum(vi const &a); vi sufSum(vi const &a); void make_set(ll v); ll find_set(ll v); void union_sets(ll a, ll b); ll const MOD = 1e9+7; ll const N = 2e5+5; ll const Ng = 2e3+5; ll const INF = 1e18; vi in(N,0); vi g[N]; vb vis(N); vi level(N,INF); vvi levelg(Ng, vi(Ng,INF)); int lp[N+1]; vector<int> pr; int dx[] = {1,-1,0,0,-1,-1,1,1}, dy[] = {0,0,1,-1,1,-1,1,-1}; vi parent(N); vi sizes(N); // vvb gvis[N][N]; // vvi g[N][N]; /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */ // use sqrtl for precise square root of long long number. // string s; // vi an; // ll ans(0); // ll n; // ll k; // ll m; struct segtree{ int size; vector<ll> sums; void init(int n) { size = 1; while(size < n) size *= 2; sums.assign(2 * size, 0LL); } void build(vi& a, int node, int lx, int rx){ // covers the range - [lx, rx). if(rx - lx == 1) { if(lx < sz(a)) sums[node] = a[lx]; return; } int mid = (lx + rx) / 2; build(a, node *2 + 1, lx, mid); build(a, node * 2 + 2, mid, rx); sums[node] = sums[node * 2 + 1] + sums[node * 2 + 2]; } void build(vi& a){ build(a, 0, 0, size); } void set(int i, ll v, int node, int lx, int rx){ if(rx - lx == 1) sums[node] += v ; else { int mid = (lx+rx)/2; if(i<mid) set(i,v,node*2+1,lx,mid); else set(i,v,node*2+2,mid,rx); sums[node]=sums[node*2+1]+sums[node*2+2]; } } void set(int i, ll v){ set(i,v,0,0,size); } ll sum(int l, int r, int node, int lx, int rx){ if(lx>=r || l>=rx) return 0; if(l<=lx&&rx<=r) return sums[node]; int mid = (lx+rx)/2; return sum(l,r,node*2+1,lx,mid)+sum(l,r,node*2+2,mid,rx); } ll sum(int l, int r){ return sum(l,r,0,0,size); } }; ll n,m; void sigma(){ cin>>n>>m; segtree sg; sg.init(n+2); vi a(n+2,0); sg.build(a); while(m--){ int q;cin>>q; if(q == 1){ ll l,r,x; cin>>l>>r>>x; sg.set(l,x); sg.set(r,-x); } else{ int i; cin>>i; cout << sg.sum(0,i+1) << '\n'; } } } signed main(){ FAST // primes(); cout << setprecision(15) << fixed; ll T = 1; // cin>>T; fi(tc,1,T+1){ debug(tc) sigma(); } } void dijkstra(ll source, vp g[], ll n) { vb vis(N,0); vi dist(N, MOD); // set<pii> q; priority_queue<pii, vp, greater<pii>> q; q.push({0,source}); dist[source] = 0; while (!q.empty()) { auto node = q.top(); q.pop(); ll v = node.second, d = node.first; if (vis[v]) continue; vis[v] = 1; for(auto child : g[v]) { int child_v = child.first, wt = child.second; if (dist[v] + wt < dist[child_v]) { dist[child_v] = dist[v] + wt; q.push({dist[child_v], child_v}); } } } } void bfs(ll source){ queue<ll> q; q.push(source); vis[source]=1; level[source] = 0; while (!q.empty()) { auto curr_v = q.front();q.pop(); // processing the source node debug(curr_v) for(auto &child : g[curr_v]) { if (!vis[child]) { q.push(child); vis[child] = 1; level[child] = level[curr_v] + 1; // visiting the child now. } } } } // DSU void make_set(ll v) { parent[v] = v; sizes[v] = 1; } ll find_set(ll v) { if (parent[v] == v) return v; return parent[v] = find_set(parent[v]); } void union_sets(ll a, ll b) { a = find_set(a); b = find_set(b); if (a!=b) { if (sizes[a] < sizes[b]) swap(a,b); parent[b] = a; // merge(a,b); sizes[a] += sizes[b]; } } void grid_dfs(ll i, ll j, vs &g, vvb &vis) { ll n = sz(g), m = sz(g[0]); if (i < 0 || i >= n || j < 0 || j >= m) { return; } if (vis[i][j]) return; debug(i) debug(j) vis[i][j]=1; fi(zz,0,4) { ll cx = i + dx[zz], cy = j + dy[zz]; grid_dfs(cx,cy,g,vis); } } void grid_bfs(ll i, ll j, vs &s) { queue<pii> q; q.push({i,j}); // auto valid = [&](ll x, ll y) // { // return x >= 0 && x < sz(s) && y >= 0 && y < sz(s[0]); // }; // vis[i][j] = 1; levelg[i][j] = 0; while (!q.empty()) { auto curr_v = q.front(); q.pop(); fi(zz,0,4) { ll cx = curr_v.first + dx[zz], cy = curr_v.second + dy[zz]; // if (!valid(cx,cy)) // { // continue; // } if (levelg[cx][cy] > 1 + levelg[curr_v.first][curr_v.second]) { levelg[cx][cy] = 1 + levelg[curr_v.first][curr_v.second]; q.push({cx,cy}); } } } } bool kahn(ll n) // for check if topological sorting is possible (only possible in case of DAGs) { vi an; pqii q; fi(i,1,n+1)if(!in[i])q.push(i); while (!q.empty()) { ll v = q.top(); q.pop(); an.em(v); for (ll u : g[v]) { in[u]--; if (!in[u]) q.push(u); } } return an.size() == n; } ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } ll binpowm(ll a, ll b, ll mod = MOD) { ll res = 1; a%=mod; while(b) { if(b & 1) res = ((__int128)res * a) % mod; a = ((__int128)a * a) % mod; b >>= 1; } return res; } string bin(ll x){ if (!x) { return "0"; } string s; while (x) { s += '0' + x%2; x/=2; } reverse(all(s)); return s; } void primes(){ for (int i=2; i<=N; ++i) { if (lp[i] == 0) { lp[i] = i; pr.push_back (i); } for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j) lp[i * pr[j]] = pr[j]; } } bool prmchk(ll n) { return (lp[n] == n); } vi trial_division4(ll n) { vi factorization; for (ll d : pr) { if (d * d > n) break; while (n % d == 0) { factorization.em(d); n /= d; } } if (n > 1) factorization.em(n); return factorization; } ll lcm(ll a, ll b){ return ((a*b)/__gcd(a,b)); } vi previousGreaterElement(vi &a, int n) { stack<int> s; vi x(n); fi(i,0,n) { while (!s.empty() && a[s.top()] <= a[i]) { s.pop(); } if(!s.empty() && a[i] < a[s.top()]) { x[i] = s.top(); } else x[i] = -1; s.push(i); } return x; } vi sufSum(vi const &a){ vi x=a;fr(i,sz(a)-1,0)x[i]+=x[i+1];return x; } vi preSum(vi const &a){ vi x=a;fi(i,1,sz(a))x[i]+=x[i-1];return x; } ll modi(ll x, ll m) { return binpowm(x,m-2,m); } /* Kratos is here Killer Yeah, it's crazy, I'm a (killer) Made all this money from doin' this D.A. got that dope Now count it, five, ten, yeah, fifteen, twenty Twenty-five, thirty, yeah, get the money Throw it in the furnace, yeah, this shit be funny Earn it just to burn it, swag drippin' from me That's what I do with money, got money up the ass Call it toilet paper, yeah, flushed with cash Girl, nice butt, is it up for grabs? Just wanna touch your ass, is that too much to ask? Yeah I made it grip, I know it's tough to grasp, get the bag Call it potato chips, I stuff in duffel bags On some public transportation shit, 'cause I will bust your ass Fuck the chain, I'm off the trailer hitch, I got a bunch of swag Now count it, five, ten, yeah, fifteen, twenty Twenty-five, thirty, yeah, get the money Throw it in the furnace, yeah, this shit be funny Earn it just to burn it, swag drippin' from me Yeah, I'm a (killer) Yeah, I'm a (what?), I'm a (what?), I'm a (killer) Yeah, look, yeah My income is all that and then some Girl, your man is nincompoop, a symptom Of a simp 'cause he'll spend some loot to get some As for me, I'm like Kim Jong-Un, a pimp, son Swag dripping, I'm in a pub Went up to this chick, who was so tipsy, we went to hug Ended up tripping, I picked her up She yelled out it's her birthday She's fifty and in the club Then it comes on (yeah), that "In da Club" song (yeah) She's a buzzsaw (what?), we goin' numbskull (uh) I live on the edge, she's a jump off (yeah) Call her Cinderella (why?), she loves balls (oh) Now count it, five, ten, yeah, fifteen, twenty Twenty-five, thirty, yeah, get the money Throw it in the furnace, yeah, this shit be funny Earn it just to burn it, swag drippin' from me Yeah, I'm a (killer) Attack like the Ripper All over the track doin' laps like a stripper Now (now), now (now), we'll vow (vow) it out (out) Rap circles around ('round), surround sound (Sound) John Rambo's back and my ammo stacked And I'm cocking raps, I'm on your head Other words, I'm stocking caps and I'm talking facts Like OfficeMax Never down, I'll be up like an insomniac Girl, I got racks you gotta rack How you got all that back and no body fat I'm in awe with that When I stop the Pontiac at the laundry mat that I saw you at You almost had a heart attack when you met Cardiac You ran inside, told your boyfriend like, "I'll be back" But for all you know I probably act like I'm Daniel Wozniak I'm a psycho-chopathic killer I'm a cap peeler, caterpillar With the botanic of bananas you ain't never heard Better vernacular comin' after your scapular For the lack of a better word Dracula 'Cause I'm attackin' a rapper in the phrenic nerve I'm a savage back, put the dagger in the back of competitors Predator and scavenger I am a carnivore and a baller, you're at the dollar store What the fuck you got a wallet for? Y'all are poor I was livin' in squalor but uh-uh, not no more Now I'm the one they holla for Fuckin' shit up like a dinosaur in a China store Bitch, I'm number five (what?), minus four (haha) Now count it, five, ten, yeah, fifteen, twenty Twenty-five, thirty, yeah, get the money Throw it in the furnace, yeah, this shit be funny Earn it just to burn it, swag drippin' from me Yeah, I'm a (killer) Yeah, I'm a (what?), I'm a (what?), I'm a (killer) Yeah */