fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =2e5+5;
  33. const ll MOD =  1e9 + 7;
  34. void FOI(){
  35.     freopen("input.txt", "r" , stdin);
  36.     freopen("output.txt", "w" , stdout);
  37. }
  38.  
  39. //check ur idea
  40.  
  41. struct Node{
  42.     ll sum;
  43. };
  44.  
  45. struct segtree{
  46.     int size;
  47.     vector<Node> values;
  48.  
  49.     void init(int n){
  50.         size = 1;
  51.         while(size < n)size*=2;
  52.         values.resize(2 * size);
  53.     }
  54.     Node neutral_element = {0};
  55.     Node single_node(ll val){
  56.         return{ val};
  57.     }
  58.  
  59.     Node merge(Node a , Node b){
  60.         return {a.sum + b.sum};
  61.     }
  62.     void build(vector<Node> & v , int x , int lx , int rx){// build in linear time
  63.         if(rx - lx == 1){
  64.             if(lx < (int)v.size()){
  65.                values[x] = v[lx];
  66.             }
  67.             return;
  68.         }
  69.         int m = (lx + rx)/2;
  70.         build(v , 2 * x + 1 , lx , m);
  71.         build(v , 2 * x + 2 , m , rx);
  72.         values[x] = merge(values[2*x+1] , values[2*x+2]);
  73.     }
  74.     void build(vector<Node> & v){
  75.         build(v , 0 , 0 , size);   
  76.     }
  77.  
  78.     void set(int i  , ll val , int x ,  int lx , int  rx){// log(n)
  79.         if(rx - lx == 1){
  80.             values[x] = single_node(val);
  81.             return ;
  82.         }
  83.         int m = (lx + rx)/2;
  84.         if(i < m){
  85.             set(i , val , 2*x+1 ,  lx , m);
  86.         }
  87.         else{
  88.             set(i , val , 2*x+2 , m , rx);
  89.         }
  90.         values[x] = merge(values[2*x+1] , values[2*x+2]);
  91.     }
  92.     void set(int i  , ll val){
  93.         set(i , val , 0 , 0 , size);
  94.     }
  95.     Node query(int l , int r , int x , int lx , int rx){// log(n)
  96.         if(lx >= l && rx <= r) return values[x];
  97.         if(rx <= l || lx >= r) return neutral_element;
  98.         int m = (lx+rx)/2;
  99.         Node p1 = query(l , r , 2*x+1  , lx , m) ;
  100.         Node p2 = query(l , r , 2*x+2 , m , rx) ;
  101.         return merge(p1 , p2);
  102.     }
  103.     Node query(int l , int r){
  104.         return query(l , r , 0 , 0 , size);
  105.     }
  106. };
  107.  
  108. void solve(){
  109. int n , q;  cin >> n >> q;
  110. segtree st;
  111. st.init(n);
  112. for(int i = 0 ; i < q ; i++){
  113.     int op ; cin >> op;
  114.     if(op == 1){
  115.         int l , r ;ll v; cin  >> l >> r >> v;
  116.         st.set(l , v) ;
  117.         if(r < n)
  118.         st.set(r , -v);
  119.     }
  120.     else{
  121.         int idx;
  122.         cin >> idx;
  123.         cout << st.query(0 , idx+1).sum << '\n';
  124.     }
  125. }
  126.  
  127. }
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135. int main() {
  136.  
  137.  
  138.     IOF
  139.  
  140.     ll t = 1;
  141.     //cin >> t;
  142.     while (t--) {
  143.  
  144.     solve() ;
  145.  
  146.     }
  147.  
  148.     return 0;
  149. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ylYsaD
language:
C++ (gcc 8.3)
created:
273 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!