Submission #1293450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293450		qrn	새로운 문제 (POI11_met)	C++20	74 / 100	5241 ms	83816 KiB

met

//ome47
#include "bits/stdc++.h"
using namespace std;
#define intt long long

const intt mxN = 5e5 + 5;
const intt LG = 20;
const intt inf = 1e18;  


intt n, m, k;
vector<intt> a(mxN), need(mxN), seg(4 * mxN), lazy(4 * mxN), mid(mxN);
vector<vector<intt>> idx, f;
vector<pair<intt,intt>> boo;
vector<array<intt,3>> sh;

void push(intt node, intt l, intt r) {
    if(!lazy[node]) return;
    seg[node] += (r - l + 1) * lazy[node];
    if(l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void upd(intt node, intt l, intt r, intt ql, intt qr, intt val) {
    push(node, l, r);
    if(ql > r || qr < l || ql > qr) return;
    if(ql <= l && r <= qr) {
        lazy[node] += val;
        push(node, l, r);
        return;
    }

    intt mid = (l + r) / 2;
    upd(node * 2, l, mid, ql, qr, val);
    upd(node * 2 + 1, mid + 1, r, ql, qr, val);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

intt get(intt node, intt l, intt r, intt ql, intt qr) {
    push(node, l, r);
    if(ql > r || qr < l || ql > qr) return 0ll;
    
    if(ql <= l && r <= qr) {
        push(node, l, r);
        return seg[node];
    }
    intt mid = (l + r) / 2;
    return get(node * 2, l, mid, ql, qr) + get(node * 2 + 1, mid + 1, r, ql, qr);
}

void _() {
    cin >> n >> m;
    idx.assign(n + 10, vector<intt> {});
    boo.assign(n + 10, {0ll,0ll});
    for(intt i = 1; i <= m; i++) {
        cin >> a[i];
        idx[a[i]].push_back(i);
    }
    for(intt i = 1; i <= n; i++) {
        cin >> need[i];
    }
    cin >> k;

    sh.push_back({-1,-1});
    for(intt i = 0; i < k; i++) {
        intt l, r, a;
        cin >> l >> r >> a;
        sh.push_back({l, r, a});
    }

    for(intt i = 1; i <= n; i++) {
        boo[i] = {1, k};
    }

    vector<intt> ans(n + 1, -1);
    for(intt reps = 0; ; reps++) {
        seg.assign(4 * m + 50, 0ll);
        lazy.assign(4 * m + 50, 0ll);
        f.assign(k + 30, vector<intt> {});
        bool c = 0;
        for(intt i = 1; i <= n; i++) {
            if(boo[i].first <= boo[i].second) {
                c=1;
            } 
            mid[i] = (boo[i].first + boo[i].second) / 2;
            f[(boo[i].first + boo[i].second) / 2].push_back(i);
        }
        if(!c) break;

        for(intt s = 1; s <= k; s++) {
            if(sh[s][0] <= sh[s][1]) {
                upd(1, 1, m, sh[s][0], sh[s][1], sh[s][2]);
            } else {
                upd(1, 1, m, sh[s][0], m, sh[s][2]);
                upd(1, 1, m, 1, sh[s][1], sh[s][2]);
            }

            intt amiri=0;
            for(intt i = 0; i < (intt)f[s].size(); i++) {
                intt p = f[s][i];
                for(intt j = 0; j < (intt)idx[p].size(); j++) {
                    amiri += get(1, 1, m, idx[p][j], idx[p][j]);
                    if(need[p] <= amiri) {
                        break;
                    }
                }
                if(amiri >= need[p]) {
                    ans[p] = mid[p];
                    boo[p].second = mid[p] - 1;
                } else {
                    boo[p].first = mid[p] + 1;
                }
                amiri = 0;
            }
        }
    }

    for(intt i = 1; i <= n; i++) {
        if(ans[i] == -1) {
            cout << "NIE" << endl;
        } else {
            cout << ans[i] << endl;
        }
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1;
    // cin >> t;
    while(t--){
        cout << endl;
        _();
    }
}
// ⠀⠀⠀⠀⠀⠀⠀⢀⣤⣦⣶⣤⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣤⢀⣀⡀⣠⣄⣠⣶⣿⣿⣿⣿⣿⣿⣿⣷⣾⡦⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠻⡳⢛⠛⠒⠚⢛⣿⣿⠟⠋⠉⠛⠛⢿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀
// ⢛⡛⢿⣿⠟⠻⠛⣿⣇⣶⣖⣤⣀⣄⡰⣹⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀
// ⢿⠿⠿⠿⠿⠿⠿⢭⣐⠠⢼⣬⠽⢈⢁⡿⠛⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣛⣱⣤⣤⣤⣀⣄⣄⣗⢌⠋⠉⢙⣴⣧⢤⣤⣤⣤⣦⡀⠀⠀⠀⠀⢺⡿
// ⣿⣿⣿⠟⠛⠋⠀⡬⠼⢠⠍⠂⠀⠨⡇⠀⡏⠉⠛⢿⣧⠀⠀⠀⠀⢸⣀
// ⣟⠄⠀⠀⠀⠀⠀⢡⠀⠀⠀⠀⠀⡠⠁⢀⠁⠀⠀⠀⠘⣗⢀⠄⢶⣼⣾
// ⠀⠀⠀⢠⣦⠇⠀⠀⠁⠒⠒⠒⠈⠀⠀⠀⣞⢶⡀⠀⠀⠹⣧⣠⡞⣸⣏
// ⠀⠀⢀⡞⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣦⡀⠀⠈⠫⣕⣻⡇
// ⠀⠀⣾⣧⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣿⣿⣿⣷⣦⡠⡤⠀⣿⡇
// ⠠⢿⣿⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠴⣿⣿⣿⣿⠟⠋⢀⣤⣿⣷
// ⣀⣀⣀⣙⣃⣠⣤⣔⣤⣢⣵⣒⣒⣢⣄⣤⣄⣛⣋⣉⣀⣀⣤⣿⣿⣿⣿

• 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