Advertisement
OIQ

Untitled

OIQ
Jan 6th, 2020
145
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7. vector <pair<int, int>> k;
  8.  
  9. int getmin(int v, int l, int r, int L, int R, vector<int> &d) {
  10.     if (l > R || r < L)
  11.         return 1000 * 1000 * 1000;
  12.     if (l >= L && r <= R)
  13.         return d[v];
  14.  
  15.     int m1 = getmin(2 * v + 1, l, (l + r) / 2, L, R, d);
  16.     int m2 = getmin(2 * v + 2, (l + r) / 2 + 1, r, L, R, d);
  17.  
  18.     return min(m1, m2);
  19. }
  20.  
  21. int main() {
  22.  
  23.     ios_base::sync_with_stdio(false);
  24.  
  25.     int n;
  26.     cin >> n;
  27.  
  28.     vector <int> v(n);
  29.     for (int i = 0; i < n; i++)
  30.         cin >> v[i];
  31.  
  32.     int m;
  33.     cin >> m;
  34.     k.resize(m);
  35.  
  36.     for (int i = 0; i < m; i++) {
  37.         int a, b;
  38.         cin >> a >> b;
  39.         k[i] = { a, b };
  40.     }
  41.  
  42.     sort(k.begin(), k.end());
  43.     vector <int> kk(m);
  44.     for (int i = 0; i < m; i++) {
  45.         kk[i] = k[i].first;
  46.     }
  47.  
  48.     //sort(kk.begin(), kk.end());
  49.     int N = pow(2, ceil(log2(m)));
  50.  
  51.     vector <int> d(2 * N - 1, 1000 * 1000 * 1000);
  52.     for (int i = d.size() / 2; i < d.size() / 2 + m; i++)
  53.         d[i] = k[i - d.size() / 2].second;
  54.  
  55.     for (int i = d.size() / 2 - 1; i >= 0; i--)
  56.         d[i] = min(d[2 * i + 1], d[2 * i + 2]);
  57.  
  58.     long long ans = 0;
  59.     for (int i = 0; i < n; i++) {
  60.         int c = lower_bound(kk.begin(), kk.end(), v[i]) - kk.begin();
  61.         ans  += getmin(0, d.size() / 2, d.size() - 1, c + d.size() / 2, d.size() - 1, d);
  62.     }
  63.     cout << ans;
  64.  
  65.     return 0;
  66. }
Advertisement
RAW Paste Data Copied
Advertisement