제출 #1203003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203003		agrim_09	Meteors (POI11_met)	C++20	큐에 대기중	0 ms	0 KiB

met

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl '\n';
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define py cout << "YES" << endl;
#define pn cout << "NO" << endl;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define int long long
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 1e18;
const ll mod = 1e9+7;


// #ifndef ONLINE_JUDGE
// #include "algo/Standard_Stuff/debug.cpp"
// #else
// #define debug(...) 42
// #endif

// void judge(){
//     srand(time(NULL));
//     #ifndef ONLINE_JUDGE
//     freopen("1.txt","r",stdin);
//     freopen("2.txt","w",stdout);
//     #endif
// }

#pragma once

template <typename T>
struct BinaryIndexedTree {
  int N;
  vector<T> data;

  BinaryIndexedTree() = default;

  BinaryIndexedTree(int size) { init(size); }

  void init(int size) {
    N = size + 2;
    data.assign(N + 1, {});
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return T{};  // return 0 if k < 0
    T ret{};
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }

  // get value of k
  inline T operator[](int k) const { return sum(k) - sum(k - 1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // range add x to [l,r]
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // minimize i s.t. sum(i) >= w

};

/**
 * @brief Binary Indexed Tree(Fenwick Tree)
 * @docs docs/data-structure/binary-indexed-tree.md
 */


struct query{
    int l,r,val;
};

// Look for edge cases!!!
signed main(){
    fastio; //judge();
    int n,m; cin >> n >> m;
    vector<int>a(m),target(n);
    vector<vector<int>> stations(n);
    for(int i = 0;i<m;i++){
        cin >> a[i]; a[i]--;
        stations[a[i]].pb(i);
    }
    for(auto &x : target) cin >> x;

    int q; cin >> q;
    vector<query>queries(q);
    for(auto &[x,y,z]:queries){
        cin >> x >> y >> z;
        x--; y--;
    }

    vector<int>ans(n,-1),left(n,0),right(n,q-1);

    int tmp_max_val = 10;
    while(true){
        vector<vector<int>>to_check(q);
        bool all_answered = true;
        for(int i = 0;i<n;i++){
            if(left[i]>right[i]){
                continue;
            }
            all_answered = false;
            to_check[(left[i]+right[i])/2].pb(i);
        }
        if(all_answered){
            break;
        }
        BinaryIndexedTree<int>bit(m);
        for(int i = 0;i<q;i++){
            int lx = queries[i].l, rx = queries[i].r, cnt = queries[i].val;
            bit.add(lx, cnt);
            if(lx<=rx){
                if(rx+1!=m){
                    bit.add(rx+1,-1*cnt);
                }
            }
            else{
                bit.add(0,cnt);
                if(rx+1!=m){
                    bit.add(rx+1,-1*cnt);
                }
            }

            for(auto state : to_check[i]){
                int sum = 0;
                for(auto idx : stations[state]){
                    sum += bit.sum(idx);
                }
                if(sum>=target[state]){
                    ans[state] = i+1;
                    right[state] = i-1;
                }
                else{
                    left[state] = i+1;
                }
            }
        }
    }
    for(auto x : ans){
        if(x==-1){
            cout << "NIE" << endl;
        }
        else{
            cout << x << endl;
        }
    }
}