fork download 
  1. // 14th CPU Problem A
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define all(v) v.begin(),v.end()
  6. #define rall(v) v.rbegin(),v.rend()
  7. #define pb push_back
  8. #define ff first
  9. #define ss second
  10. #define ok cerr<<"Line "<<__LINE__<<" : "<<"ok"<<endl
  11. #define DBG(a) cerr<< "Line "<<__LINE__ <<" : "<< #a <<" = "<<(a)<<endl
  12. #define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
  13.  
  14.  
  15. #define Gene template< class
  16. #define Rics printer& operator,
  17. Gene c> struct rge{c b, e;};
  18. Gene c> rge<c> range(c i, c j){ return {i, j};}
  19. struct printer{
  20.  ~printer(){cerr<<endl;}
  21.  Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
  22.  Rics(string x){cerr<<x;return *this;}
  23.  Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
  24.  Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
  25.  Gene c >Rics(rge<c> x){
  26.      *this,"["; for(auto it = x.b; it != x.e; ++it)
  27.          *this,(it==x.b?"":", "),*it; return *this,"]";}
  28. };
  29. #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
  30. #define dbg(x) "[",#x,": ",(x),"] "
  31. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. int my_rand(int l, int r) {
  33.  return uniform_int_distribution<int>(l, r) (rng);
  34. }
  35.  
  36.  
  37. typedef long long ll;
  38. typedef pair<int,int> pii;
  39.  
  40.  
  41.  
  42. const int N = 200009;
  43. vector< array<int,3> > operation;
  44. // 0-> value, 1->active, 2->label
  45. vector<array<int,3>> finalAr; // 1 based index,dummy insert at first
  46.  
  47. struct Node {
  48.   int value,active,label;
  49.   Node* left;
  50.   Node* right;
  51. };
  52.  
  53. map<int,Node*> nodeMap;
  54. map<int,int> labelToIdx;
  55.  
  56. Node* head = nullptr;
  57. Node* tail = nullptr;
  58.  
  59. void append(int val, int label) {
  60.  
  61.     Node* newNode = new Node();
  62.     newNode->value = val;
  63.     newNode->active = 1;
  64.     newNode-> label = label;
  65.     newNode->left = nullptr;
  66.     newNode->right = nullptr;
  67.  
  68.     nodeMap[val] = newNode;
  69.  
  70.     if (head == nullptr) {
  71.         head = tail = newNode;
  72.     } else {
  73.         tail->right = newNode;
  74.         newNode->left = tail;
  75.         tail = newNode;
  76.     }
  77. }
  78.  
  79. void insertAfter(int newVal,int existingVal, int label) {
  80.   Node* existingNode = nodeMap[existingVal];
  81.  
  82.   Node* newNode = new Node();
  83.   newNode -> value = newVal;
  84.   newNode->active = 1;
  85.   newNode-> label = label;
  86.   newNode -> left = existingNode;
  87.   newNode -> right = existingNode -> right;
  88.  
  89.   // Update Links
  90.   if (existingNode -> right != nullptr) {
  91.     existingNode -> right -> left = newNode;
  92.   } else {
  93.     tail = newNode;
  94.   }
  95.   existingNode->right = newNode;
  96.  
  97.   nodeMap[newVal] = newNode;
  98. }
  99.  
  100. void insertBefore(int newVal,int existingVal, int label) {
  101.  
  102.  
  103.     Node* existingNode = nodeMap[existingVal];
  104.  
  105.     Node* newNode = new Node();
  106.     newNode->value = newVal;
  107.     newNode->active = 1;
  108.     newNode->label = label;
  109.     newNode->right = existingNode;
  110.     newNode->left = existingNode->left;
  111.  
  112.  
  113.     if (existingNode->left != nullptr) {
  114.         existingNode->left->right = newNode;
  115.     } else {
  116.         head = newNode;
  117.     }
  118.     existingNode->left = newNode;
  119.  
  120.     nodeMap[newVal] = newNode;
  121. }
  122.  
  123. void remove(int val) {
  124.     Node* target = nodeMap[val];
  125.  
  126.     target -> active = 0;
  127.     // if (target->left != nullptr) {
  128.     //     target->left->right = target->right;
  129.     // } else {
  130.     //     head = target->right;  
  131.     // }
  132.  
  133.     // if (target->right != nullptr) {
  134.     //     target->right->left = target->left;
  135.     // } else {
  136.     //     tail = target->left;
  137.     // }
  138.  
  139.     // Remove from map and free memory
  140.     nodeMap.erase(val);
  141.     // delete target;
  142. }
  143.  
  144.  
  145. void buildFinalArray() {
  146.     finalAr.clear();
  147.     // 1 base index, push a dummy value;
  148.     finalAr.push_back({-1,-1,-1});
  149.  
  150.     Node* cur = head;
  151.     int idx = 1;
  152.     while (cur != nullptr) {
  153.         // cout << curr->value;
  154.         finalAr.push_back({cur->value,cur->active,cur->label});
  155.         labelToIdx[cur->label] = idx++;
  156.         cur = cur->right;
  157.     }
  158.  
  159.     // for(int i = 0; i < (int)finalAr.size(); i++){
  160.     //   cout << "( " << finalAr[i][0] << " " << finalAr[i][1] << " ";
  161.     //   cout << finalAr[i][2] << ") ";
  162.     // }
  163.     // cout << endl;
  164. }
  165.  
  166. // ====== Segment Tree Portion ======
  167. // idx 0 : sum, idx 1: count
  168. ll treeInfo[N*4][2];
  169.  
  170. void build(int n,int b,int e) {
  171.   if (b == e) {
  172.     treeInfo[n][0] = treeInfo[n][1] = 0;
  173.     if (finalAr[b][1] == 1) {
  174.       treeInfo[n][0] = finalAr[b][0];
  175.       treeInfo[n][1] =1;
  176.     }
  177.     return;
  178.   }
  179.  
  180.   int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  181.   build(l, b, mid);
  182.   build(r, mid + 1, e);
  183.   //merge
  184.   treeInfo[n][0] = treeInfo[l][0] + treeInfo[r][0];
  185.   treeInfo[n][1] = treeInfo[l][1] + treeInfo[r][1];
  186. }
  187.  
  188. void update(int n,int b,int e, int idx, int value)
  189. {
  190.   if (b > idx || e < idx) return;
  191.   if (b == e && b == idx) {
  192.     treeInfo[n][0] = value;
  193.     if (value > 0) {
  194.       treeInfo[n][1] = 1;
  195.     }
  196.     else treeInfo[n][1] = 0;
  197.  
  198.     return;
  199.   }
  200.  
  201.   int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  202.   update(l,b,mid,idx,value);
  203.   update(r,mid+1,e,idx,value);
  204.  
  205.   //merge
  206.   treeInfo[n][0] = treeInfo[l][0] + treeInfo[r][0];
  207.   treeInfo[n][1] = treeInfo[l][1] + treeInfo[r][1];
  208. }
  209.  
  210. // return sum of first m element
  211. ll query(int n,int b,int e, int m)
  212. {
  213.   if (treeInfo[n][1] == m) return treeInfo[n][0];
  214.  
  215.   int mid = (b + e) >> 1, l = n << 1, r = l | 1;
  216.   if (treeInfo[l][1] > m) {
  217.     return query(l,b,mid,m);
  218.   } else {
  219.     return treeInfo[l][0] + query(r,mid+1,e, m - treeInfo[l][1]);
  220.   }
  221. }
  222.  
  223. int main()
  224. {
  225.   // fastio;
  226.   int q,first;
  227.   cin >> q >> first;
  228.  
  229.   append(first,0);
  230.   map<int,int> labelLook;
  231.   labelLook[first] = 0;
  232.   operation.push_back({-1,first,-1});
  233.  
  234.   for(int i = 1; i <= q; i++){
  235.     int typ = 0, l = -1, r = -1;
  236.     cin >> typ;
  237.  
  238.     if (typ == 3) {
  239.       cin >> l;
  240.       remove(l);
  241.       operation.push_back({typ,l,labelLook[l]});
  242.       labelLook.erase(l);
  243.     } 
  244.     else {
  245.  
  246.       cin >> l >> r;
  247.  
  248.       if (typ == 1) {
  249.  
  250.         insertBefore(l,r,i);
  251.         labelLook[l] = i;
  252.       }
  253.       else if(typ == 2) {
  254.         insertAfter(l,r,i);
  255.         labelLook[l] = i;
  256.       }
  257.       operation.push_back({typ,l,r});
  258.     }
  259.  
  260.   }
  261.  
  262.   buildFinalArray();
  263.  
  264.   // build update query
  265.   int n = finalAr.size() - 1;
  266.   build(1,1,n);
  267.  
  268.   vector<ll> output;
  269.  
  270.   for(int i = operation.size()-1; i >= 1; i--) {
  271.     int typ = operation[i][0];
  272.     int l = operation[i][1];
  273.     int r = operation[i][2];
  274.  
  275.     if (typ == 1 || typ == 2) {
  276.       int idx = labelToIdx[i];
  277.       update(1,1,n,idx,0);
  278.     }
  279.     else if (typ == 3) {
  280.       int idx = labelToIdx[r]; // r is the label of removing numbr
  281.       update(1,1,n,idx,l); // l is the value of removed number, as we iterate reverse. add the number
  282.     }
  283.     else if (typ == 4) {
  284.       ll ans = query(1,1,n,r) - query(1,1,n,l-1);
  285.       output.push_back(ans);
  286.     }
  287.   }
  288.  
  289.  
  290.   for(int i = output.size()-1; i >= 0; i--){
  291.     cout << output[i] << "\n";
  292.   }
  293.  
  294.  
  295.   return 0;
  296. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 3
1 5 3
2 2 3
4 1 2
3 5
4 1 2
stdout 
8
5
https://ideone.com/I5UZYa
language:
C++ (gcc 8.3)
created:
18 hours 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!