제출 #1263662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263662		nathlol2	Meteors (POI11_met)	C++20	74 / 100	4309 ms	65784 KiB

met

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int seg[4 * N], lazy[4 * N], a[N], ml[N], mr[N], mx[N], l[N], r[N], mid[N] ,ans[N];
vector<vector<int>> pos(N), ask(N);
void push(int nd, int l, int r){
    if(lazy[nd] != 0){
        seg[nd] += lazy[nd];
        if(l != r){
            lazy[nd * 2] += lazy[nd];
            lazy[nd * 2 + 1] += lazy[nd];
        }
        lazy[nd] = 0;
    }
}
void upd(int nd, int l, int r, int L, int R, int x){
    push(nd, l, r);
    if(r < L || l > R) return;
    if(l >= L && r <= R){
        lazy[nd] += x;
        push(nd, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(nd * 2, l, mid, L, R, x);
    upd(nd * 2 + 1, mid + 1, r, L, R, x);
}
int qry(int nd, int l, int r, int idx){
    push(nd, l, r);
    if(l == r){
        return seg[nd];
    }
    int mid = (l + r) / 2;
    if(idx <= mid){
        return qry(nd * 2, l, mid, idx);
    }else{
        return qry(nd * 2 + 1, mid + 1, r, idx);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    for(int i = 1;i<=m;i++){
        int x;
        cin >> x;
        pos[x].push_back(i);
    }
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    int k;
    cin >> k;
    for(int i = 1;i<=k;i++){
        cin >> ml[i] >> mr[i] >> mx[i];
    }
    for(int i = 1;i<=n;i++){
        l[i] = 1, r[i] = k, ans[i] = -1;
    }
    while(1){
        bool f = 1;
        memset(seg, 0, sizeof seg);
        memset(lazy, 0, sizeof lazy);
        ask.assign(k + 2, {});
        for(int i = 1;i<=n;i++){
            if(l[i] <= r[i]){
                f = 0;
            }
            mid[i] = (l[i] + r[i]) / 2;
            ask[mid[i]].push_back(i);
        }
        if(f){
            break;
        }
        for(int i = 1;i<=k;i++){
            if(ml[i] <= mr[i]){
                upd(1, 1, m, ml[i], mr[i], mx[i]);
            }else{
                upd(1, 1, m, ml[i], m, mx[i]);
                upd(1, 1, m, 1, mr[i], mx[i]);
            }
            // cout << "segtree\n";
            // for(int j = 1;j<=m;j++){
            //     cout << qry(1, 1, m, j) << ' ';
            // }
            // cout << '\n';
            for(auto x : ask[i]){
                int s = 0;
                for(auto p : pos[x]){
                    s += qry(1, 1, m, p);
                }
                if(s >= a[x]){
                    ans[x] = mid[x];
                    r[x] = mid[x] - 1; 
                }else{
                    l[x] = mid[x] + 1;
                }
            }
        }
    }
    for(int i = 1;i<=n;i++){
        if(ans[i] == -1){
            cout << "NIE\n";
        }else{
            cout << ans[i] << '\n';
        }
    }
}

• 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