ulvis.paste.net

Paste Search Dynamic
Recent pastes
split
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <bitset>
  6. #include <sstream>
  7. #include <iterator>
  8. #include <ctime>
  9.  
  10. using namespace std;
  11.  
  12. #define DEBUG_MODE true
  13. #define loop(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
  14.  
  15. typedef  long long ll;
  16. typedef vector<int> vi;
  17. typedef vector<vector<int> > vvi;
  18. typedef vector<pair<int, int> > vpi;
  19. typedef vector<vector<long long>> vvll;
  20. typedef unsigned long ul;
  21. typedef unsigned int ui;
  22.  
  23. const ui INF = 4294967295;
  24.  
  25. const int MOD = 1000000000;
  26.  
  27. template<typename T>
  28. void print(T a) {
  29.     loop(i, 0, a.size())
  30.         cout << a[i] << " ";
  31.     cout << endl;
  32. }
  33.  
  34. template<typename T>
  35. void print2(T a) {
  36.     loop(i, 0, a.size()) {
  37.         loop(j, 0, a[i].size())
  38.             cout << a[i][j] << " ";
  39.         cout << endl;
  40.     }
  41.     cout << endl;
  42. }
  43.  
  44. struct Treap {
  45.     ll y, c;
  46.     ll s;
  47.     Treap* left;
  48.     Treap* right;
  49. };
  50.  
  51. Treap* update(Treap* t) {
  52.     ll s1 = 0, s2 = 0;
  53.     if (t->left != nullptr) {
  54.         s1 = t->left->s;
  55.     }
  56.     if (t->right != nullptr) {
  57.         s2 = t->right->s;
  58.     }
  59.     t->s = s1 + s2 + t->c;
  60.     return t;
  61. }
  62.  
  63. pair<Treap*, Treap*> split(Treap* t, int k) {
  64.     if (!t)
  65.         return make_pair(t, t);
  66.     if (t->c > k) {
  67.         pair<Treap*, Treap*> tt = split(t->left, k);
  68.         t->left = tt.second;
  69.         t = update(t);
  70.         return make_pair(tt.first, t);
  71.     }
  72.     else {
  73.         pair<Treap*, Treap*> tt = split(t->right, k);
  74.         t->right = tt.first;
  75.         t = update(t);
  76.         return make_pair(t, tt.second);
  77.     }
  78. }
  79.  
  80. Treap* merge(Treap* t1, Treap* t2) {
  81.     if (!t1)
  82.         return t2;
  83.     if (!t2)
  84.         return t1;
  85.     if (t1->y > t2->y) {
  86.         t1->right = merge(t1->right, t2);
  87.         t1 = update(t1);
  88.         return t1;
  89.     }
  90.     else {
  91.         t2->left = merge(t1, t2->left);
  92.         t2 = update(t2);
  93.         return t2;
  94.     }
  95. }
  96.  
  97. Treap* add(Treap* t, int i) {
  98.     pair<Treap*, Treap*> t1 = split(t, i - 1);
  99.     pair<Treap*, Treap*> t2 = split(t1.second, i);
  100.     if (t2.first) {
  101.         t = merge(t2.first, t2.second);
  102.         return merge(t1.first, t);
  103.     }
  104.     Treap* node = new Treap;
  105.     node->c = i;
  106.     node->y = rand() % MOD;
  107.     node->s = i;
  108.     node->left = nullptr;
  109.     node->right = nullptr;
  110.     if (!t1.first && !t1.second)
  111.         return node;
  112.     t = merge(node, t2.second);
  113.     return merge(t1.first, t);
  114. }
  115.  
  116. ll _sum(Treap* t, int l, int r) {
  117.     if (t == nullptr)
  118.         return 0;
  119.     pair<Treap*, Treap*> t1 = split(t, l - 1);
  120.     pair<Treap*, Treap*> t2 = split(t1.second, r);
  121.     ll res = 0;
  122.     if (t2.first)
  123.         res = t2.first->s;
  124.     t = merge(t2.first, t2.second);
  125.     t = merge(t1.first, t);
  126.     return res;
  127. }
  128.  
  129. int main() {
  130.     //freopen("salesman.in", "r", stdin);
  131.     //freopen("salesman.out", "w", stdout);
  132.     srand(time(null));
  133.     int n;
  134.     cin >> n;
  135.      
  136.     char c, prev_c = '.';
  137.     ll prev_y = 0;
  138.     int a, b;
  139.     Treap* head = nullptr;
  140.     for (int i = 0; i < n; i++) {
  141.         cin >> c;
  142.         if (c == '+') {
  143.             cin >> a;
  144.             if (prev_c == '?') {
  145.                 head = add(head, ((ll)a + prev_y) % (ll)MOD);
  146.             }
  147.             else {
  148.                 head = add(head, a);
  149.             }
  150.         }
  151.         else {
  152.             cin >> a >> b;
  153.             prev_y = _sum(head, a, b);
  154.             cout << prev_y << endl;
  155.         }
  156.         prev_c = c;
  157.     }
  158.     //system("pause");
  159.     return 0;
  160. }
Parsed in 0.028 seconds