SHARE
TWEET

Untitled

a guest Feb 22nd, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <ctime>
  4. #include <cmath>
  5. #include <sstream>
  6. #include <complex>
  7. #include <fstream>  
  8. #include <bitset>
  9. #include <chrono>
  10. #include <random>
  11. #include <fstream>
  12. #include <assert.h>
  13. #include <vector>
  14. #include <set>
  15. #include <map>
  16. #include <unordered_set>
  17. #include <unordered_map>
  18. #include <queue>
  19. #include <deque>
  20. #include <algorithm>
  21. #include <stack>
  22. #include <string>      
  23.  
  24. using namespace std;
  25.  
  26. mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
  27.  
  28. typedef long long ll;
  29. typedef long double ld;
  30.  
  31. const int INF = 1e9 + 5, M = 998244353, SIZE = 1.7e7;
  32. const ld eps = 1e-8;
  33. ll INF_LL = 1e18;
  34.  
  35. /*#pragma GCC optimize("Ofast")
  36. #pragma GCC optimize("unroll-loops")
  37. #pragma GCC optimize("no-stack-protector")
  38. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  39. #pragma GCC optimize("fast-math")*/
  40.  
  41. struct Node {
  42.     int add;
  43.     int l, r;
  44.  
  45.     Node() {
  46.         add = 0;
  47.         l = r = -1;
  48.     }
  49. };
  50.  
  51. Node tree[SIZE];
  52. int tree_sz = 0;
  53.  
  54. int add() {
  55.     tree[tree_sz] = Node();
  56.     tree_sz++;
  57.     return tree_sz - 1;
  58. }
  59.  
  60. int clone(int i) {
  61.     tree[tree_sz] = tree[i];
  62.     tree_sz++;
  63.     return tree_sz - 1;
  64. }
  65.  
  66. void build(int i, int L, int R) {
  67.     if (L + 1 == R)
  68.         return;
  69.  
  70.     int m = (L + R) >> 1;
  71.     tree[i].l = add();
  72.     tree[i].r = add();
  73.  
  74.     build(tree[i].l, L, m);
  75.     build(tree[i].r, m, R);
  76. }
  77.  
  78. int mod(int i, int L, int R, int l, int r, ll x) {
  79.     if (r <= L || R <= l)
  80.         return i;
  81.  
  82.     int v = clone(i);
  83.     if (l <= L && R <= r) {
  84.         if (tree[v].add > INF)
  85.             return v;
  86.         tree[v].add += x;
  87.         return v;
  88.     }
  89.  
  90.     int m = (L + R) >> 1;
  91.  
  92.     tree[v].l = mod(tree[v].l, L, m, l, r, x);
  93.     tree[v].r = mod(tree[v].r, m, R, l, r, x);
  94.  
  95.     return v;
  96. }
  97.  
  98. void get(int i, int L, int R, int ind, ll &ans) {
  99.     ans += tree[i].add;
  100.     if (L + 1 == R)
  101.         return;
  102.     int m = (L + R) >> 1;
  103.     if (ind < m)
  104.         get(tree[i].l, L, m, ind, ans);
  105.     else
  106.         get(tree[i].r, m, R, ind, ans);
  107. }
  108.  
  109. int main() {
  110. #ifdef LOCAL
  111.     freopen("input.txt", "r", stdin);
  112.     freopen("output.txt", "w", stdout);
  113. #endif
  114.     ios::sync_with_stdio(0);
  115.  
  116.     int n, m, k;
  117.     cin >> n >> m;
  118.  
  119.     vector<int> v(1, 0);
  120.     v[0] = add();
  121.     build(0, 0, m);
  122.  
  123.     vector<vector<int>> se(m);
  124.     for (int i = 0; i < m; i++) {
  125.         int o;
  126.         cin >> o;
  127.         o--;
  128.  
  129.         se[o].push_back(i);
  130.     }
  131.  
  132.     vector<ll> p(n);
  133.     for (int i = 0; i < n; i++)
  134.         cin >> p[i];
  135.  
  136.     cin >> k;
  137.  
  138.     for (int i = 0; i < k; i++) {
  139.         int l, r, a;
  140.         cin >> l >> r >> a;
  141.         l--;
  142.  
  143.         if (l < r) {
  144.             v.push_back(mod(v.back(), 0, m, l, r, a));
  145.         }
  146.         else {
  147.             v.push_back(mod(v.back(), 0, m, l, m, a));
  148.             v.back() = mod(v.back(), 0, m, 0, r, a);
  149.         }
  150.     }
  151.  
  152.     for (int i = 0; i < n; i++) {
  153.         ll sum = 0;
  154.         for (int j : se[i])
  155.             get(v.back(), 0, m, j, sum);
  156.  
  157.         if (sum < p[i]) {
  158.             cout << "NIE\n";
  159.             continue;
  160.         }
  161.  
  162.         int l = 0, r = v.size();
  163.  
  164.         while (l + 1 < r) {
  165.             int mid = (l + r) >> 1;
  166.  
  167.             sum = 0;
  168.             for (int j : se[i])
  169.                 get(v[mid], 0, m, j, sum);
  170.  
  171.             if (sum >= p[i]) {
  172.                 r = mid;
  173.             }
  174.             else {
  175.                 l = mid;
  176.             }
  177.         }
  178.  
  179.         cout << r << '\n';
  180.     }
  181.  
  182.     return 0;
  183. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top