paulomiranda98

Untitled

Feb 20th, 2021
882
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14. const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
  15. const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
  16.  
  17. const int MAXN = 300010;
  18. typedef long long t_bit;
  19. t_bit bit[MAXN];
  20. //1-indexed
  21. t_bit get(int i){
  22.   t_bit s = 0;
  23.   for (; i > 0; i -= (i & -i))
  24.     s += bit[i];
  25.   return s;
  26. }
  27. //1-indexed
  28. void add(int i, t_bit value){
  29.   assert(i > 0);
  30.   for (; i < MAXN; i += (i & -i))
  31.     bit[i] += value;
  32. }
  33. void add(int l, int r, t_bit val){
  34.   if(l <= r){
  35.     add(l, val);
  36.     add(r+1, -val);
  37.   }else{
  38.     add(l, val);
  39.     add(1, val);
  40.     add(r+1, -val);
  41.   }
  42. }
  43. typedef tuple<int, int, int> tp;
  44.  
  45. vector<int> pos[MAXN];
  46. int p[MAXN], ans[MAXN];
  47. tp q[MAXN];
  48.  
  49. void solve(int i, int j, vector<int> &v){
  50.   if(i == j){
  51.     for(int x: v)
  52.       ans[x] = i;
  53.     return;
  54.   }
  55.   int mid = (i+j)/2;
  56.   for(int k=i; k<=mid; k++){
  57.     auto [l, r, a] = q[k];
  58.     add(l, r, a);
  59.   }
  60.   vector<int> left, right;
  61.   for(int x: v){
  62.     ll sum = 0;
  63.     for(int y: pos[x]){
  64.       sum += get(y);
  65.       if(sum >= p[x])
  66.         break;
  67.     }
  68.     if(sum >= p[x])
  69.       left.push_back(x);
  70.     else
  71.       right.push_back(x);
  72.   }
  73.   v.clear();
  74.   solve(mid+1, j, right);
  75.   for(int k=mid; k>=i; k--){
  76.     auto [l, r, a] = q[k];
  77.     add(l, r, -a);
  78.   }
  79.   solve(i, mid, left);
  80. }
  81. int main() {
  82.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  83.  
  84.   int n, m;
  85.   cin >> n >> m;
  86.   for(int i=1; i<=m; i++){
  87.     int x;
  88.     cin >> x;
  89.     pos[x].push_back(i);
  90.   }
  91.   for(int i=1; i<=n; i++){
  92.     cin >> p[i];
  93.   }
  94.   int k;
  95.   cin >> k;
  96.   for(int i=1; i<=k; i++){
  97.     int l, r, a;
  98.     cin >> l >> r >> a;
  99.     q[i] = tp(l, r, a);
  100.   }
  101.   q[k+1] = tp(1, m, 1e9);
  102.  
  103.   vector<int> v(n);
  104.   iota(all(v), 1);
  105.   solve(1, k+1, v);
  106.  
  107.   for(int i=1; i<=n; i++){
  108.     if(ans[i] > k)
  109.       cout << "NIE" << endl;
  110.     else
  111.       cout << ans[i] << endl;
  112.   }
  113.   return 0;
  114. }
  115.  
RAW Paste Data