Submission #1160601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160601		htg1616	Meteors (POI11_met)	C++20	74 / 100	2195 ms	32504 KiB

met

#include <bits/stdc++.h>
#define endl '\n'
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T>
class segment_tree{
    int n;
    vector<T> tree;

    void init(int v, int tl, int tr, const vector<T>& a){
        if(tr-tl == 1) tree[v] = a[tl];
        else{
            int tm = (tl+tr)/2;
            init(2*v, tl, tm, a);
            init(2*v+1, tm, tr, a);
        }
    }

    void update(int v, int tl, int tr, int l, int r, T x){
        if(r<=tl || tr<=l) return;
        if(l<=tl && tr<=r){
            tree[v] += x;
            return;
        }
        int tm = (tl+tr)/2;
        update(2*v, tl, tm, l, r, x);
        update(2*v+1, tm, tr, l, r, x);
    }

    T query(int v, int tl, int tr, int i){
        if(tr-tl == 1) return tree[v];
        int tm = (tl+tr)/2;
        if(i < tm) return tree[v] + query(2*v, tl, tm, i);
        else return tree[v] + query(2*v+1, tm, tr, i);
    }

public:
    segment_tree(int n_=1<<18){
        n = n_;
        tree.resize(4*n);
        vector<T> a(n);
        init(1, 0, n, a);
    }
    
    void update(int l, int r, T x){
        update(1, 0, n, l, r, x);
    }

    T query(int i){
        return query(1, 0, n, i);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    //input
    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    vector<vector<int>> o(n);
    for(int i=0; i<m; i++){
        int num;
        cin >> num; num--; //회원국 번호 0 index 사용
        o[num].push_back(i);
    }
    for(int i=0; i<n; i++) cin >> p[i];
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    vector<ll> a(q); //운석 수 ll 사용하기
    for(int i=0; i<q; i++){
        cin >> l[i] >> r[i] >> a[i];
        l[i]--, r[i]--; //운석 위치 0 index 사용
    }

    vector<int> start(n), end(n, q+1); //날짜 1 index 사용
    while(true){
        bool flag = true;
        vector<vector<int>> check(q+1);
        for(int i=0; i<n; i++){
            if(start[i]+1 < end[i]){
                flag = false;
                check[(start[i]+end[i])/2].push_back(i);
            }
        }
        if(flag) break;

        segment_tree<ll> seg(m);
        for(int i=0; i<q; i++){
            if(l[i]<=r[i]) seg.update(l[i], r[i]+1, a[i]); //세그먼트 트리는 반열린구간 사용함
            else{
                seg.update(l[i], m, a[i]);
                seg.update(0, r[i]+1, a[i]);
            }
            for(int j: check[i+1]){
                ll cnt = 0;
                for(int pos: o[j]) cnt += seg.query(pos);
                if(cnt >= p[j]) end[j] = i+1;
                else start[j] = i+1;
            }
        }
    }

    for(int i=0; i<n; i++){
        if(end[i] == q+1) cout << "NIE" << endl;
        else cout << end[i] << endl;
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13