fork download
copy 
  1. #include <bits/stdc++.h>
  2. struct Sqrt{
  3.     long long *a, *b;
  4.     int SQ;
  5.     explicit Sqrt(int n){
  6.         SQ = (int)sqrt(n) + 1;
  7.         a = new long long[n]{};
  8.         b = new long long[SQ]{};
  9.     }
  10.     ~Sqrt() = default;
  11.     void update(int r, long long v) const {
  12.         for(int j=0; j<r/SQ; ++j)
  13.             b[j] += v;
  14.         for(int i=(r/SQ)*SQ; i<r; ++i)
  15.             a[i] += v;
  16.     }
  17.     void update(int l, int r, long long v) const {
  18.         update(r, v);
  19.         update(l, -v);
  20.     }
  21.     [[nodiscard]] long long get(int i) const{
  22.         return b[i/SQ] + a[i];
  23.     }
  24. };
  25. struct Query{
  26.     int op, a, b;
  27.     long long x, p;
  28. };
  29. int main() {
  30.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  31.     int n, q;
  32.     std::cin >> n >> q;
  33.     Query b[n+q];
  34.     for(int i=0; i<n; ++i)
  35.         std::cin >> b[i].p >> b[i].a >> b[i].b, b[i].op = 1;
  36.     std::vector<long long> numbers;
  37.     std::map<long long, int> flatten;
  38.     for(int j=n; j-n<q; ++j){
  39.         std::cin >> b[j].op;
  40.         if(b[j].op == 1)
  41.             std::cin >> b[j].p >> b[j].a >> b[j].b;
  42.         else {
  43.             std::cin >> b[j].x;
  44.             numbers.push_back(b[j].x);
  45.         }
  46.     }
  47.     std::sort(numbers.begin(), numbers.end());
  48.     numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end());
  49.     int m = numbers.size();
  50.     for(int c=0; c<m; ++c)
  51.         flatten[numbers[c]] = c;
  52.     Sqrt st(m);
  53.     for(int i=0; i<m; ++i)
  54.         st.update(i,i+1,numbers[i]);
  55.     for(int j=0; j<q+n; ++j) {
  56.         if(b[j].op == 1){
  57.             int l{}, r{m};
  58.             while(l<=r){
  59.                 int k = (l+r)/2;
  60.                 if(st.get(k) < b[j].p)
  61.                     l = k + 1;
  62.                 else
  63.                     r = k - 1;
  64.             }
  65.             st.update(0, l, -b[j].b);
  66.             st.update(l, m, b[j].a);
  67.         }
  68.         else{
  69.             std::cout << st.get(flatten[b[j].x]) << '\n';
  70.         }
  71.     }
  72. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 3
5 2 1
10 3 4
2 1 5
2 6
1 8 2 3
2 6
stdout
copy 
5
2
https://ideone.com/E33Bsy
language:
C++14 (gcc 8.3)
created:
1 day 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!