Advertisement
YEZAELP

SMMR-125: Inf_Array

Apr 16th, 2021 (edited)
148
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int M = 1e5;
  5. using lli = long long;
  6. using pll = pair <lli, lli>;
  7. vector <lli> pst;
  8. lli l[M+10], r[M+10], value[M+10];
  9. lli qs[4*M + 10], qss[4*M + 10]; // ระวังขนาด array เก็บ ตำแหน่ง quicksum และ query
  10. pll query[M+10];
  11. lli m, sz;
  12.  
  13. lli BinarySearch(lli val){
  14.     lli l = 0, r = sz-1;
  15.     while(l <= r){
  16.         lli mid = (l + r) / 2;
  17.         if(pst[mid] == val) return mid;
  18.         if(pst[mid] < val)
  19.             l = mid + 1;
  20.         else r = mid - 1;
  21.     }
  22. }
  23.  
  24. int main(){
  25.  
  26.     lli q;
  27.     scanf("%lld%lld", &m, &q);
  28.  
  29.     for(int i=1;i<=m;i++) {
  30.         scanf("%lld%lld%lld", &l[i], &r[i], &value[i]);
  31.         pst.push_back(l[i]);
  32.         pst.push_back(r[i]+1);
  33.     }
  34.  
  35.     for(int i=1;i<=q;i++){
  36.         lli f, s;
  37.         scanf("%lld%lld", &f, &s);
  38.         query[i] = {f-1, s};
  39.         pst.push_back(f-1);
  40.         pst.push_back(s);
  41.     }
  42.  
  43.     sort(pst.begin(), pst.end());
  44.     pst.resize( unique(pst.begin(), pst.end()) - pst.begin() );
  45.     sz = pst.size();
  46.  
  47.     for(int i=1;i<=m;i++){
  48.         lli idl = BinarySearch(l[i]);
  49.         qs[idl] += (lli) value[i];
  50.         lli idr = BinarySearch(r[i]+1);
  51.         qs[idr] -= (lli) value[i];
  52.     }
  53.  
  54.     qss[0] = qs[0];
  55.     for(int i=1;i<sz;i++){
  56.         lli dif = pst[i] - pst[i-1] - 1;
  57.         qs[i] += qs[i-1];
  58.         qss[i] = qss[i-1] + (lli) (qs[i-1] * dif) + qs[i];
  59.     }
  60.  
  61.     for(int i=1;i<=q;i++) {
  62.         lli idf = BinarySearch(query[i].first);
  63.         lli ids = BinarySearch(query[i].second);
  64.         printf("%lld\n", qss[ids] - qss[idf]);
  65.     }
  66.  
  67.     return 0;
  68. }
  69. /*
  70.  
  71. 3 2
  72. 1 2 1
  73. 3 4 2
  74. 4 6 3
  75. 1 3 4 5 7
  76. 1 2 5 3 0
  77.  
  78. 3 10
  79. 1 2 1
  80. 4 6 2
  81. 5 8 1
  82. 1 3 4 5 7 9
  83. 1 0 2 3 1 0
  84.  
  85.  
  86. 3 5
  87. 1 2 1
  88. 4 6 2
  89. 5 8 1
  90. 3 8
  91. 1 6
  92. 5 9
  93. 9 100
  94. 1 1
  95.  
  96. 10 10
  97. 1 1 1
  98. 2 2 2
  99. 3 3 3
  100. 4 4 4
  101. 5 5 5
  102. 6 6 6
  103. 7 7 7
  104. 8 8 8
  105. 9 9 9
  106. 10 10 10
  107. 1 1
  108. 2 2
  109. 3 3
  110. 4 4
  111. 5 5
  112. 6 6
  113. 7 7
  114. 8 8
  115. 9 9
  116. 10 10
  117.  
  118. 3 3
  119. 1 1 1
  120. 4 4 4
  121. 7 7 10
  122. 1 1
  123. 2 2
  124. 6 6
  125. */
  126.  
Advertisement
RAW Paste Data Copied
Advertisement