Submission #1293462

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

met

//ome47
#include "bits/stdc++.h"
using namespace std;
#define intt int
#define ll long long
#define endl "\n"

const intt mxN = 3e5 + 5;

intt n, m, k;
vector<intt> a(mxN), mid(mxN);
vector<ll> need, seg, lazy;           
vector<vector<intt>> idx, f;
vector<pair<intt,intt>> boo;
vector<array<ll,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, ll 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 md = (l + r) / 2;
    upd(node * 2, l, md, ql, qr, val);
    upd(node * 2 + 1, md + 1, r, ql, qr, val);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

ll 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 md = (l + r) / 2;
    return get(node * 2, l, md, ql, qr) + get(node * 2 + 1, md + 1, r, ql, qr);
}

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

    need.assign(n + 10, 0ll);
    for(intt i = 1; i <= n; i++) {
        cin >> need[i];
    }
    cin >> k;

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

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

    vector<intt> ans(n + 1, -1);
    for(;;) {
        seg.assign(4 * m + 50, 0ll);
        lazy.assign(4 * m + 50, 0ll);
        f.assign(k + 30, vector<intt> {});
        bool c = false;
        for(intt i = 1; i <= n; i++) {
            if(boo[i].first <= boo[i].second) {
                c = true;
                mid[i] = (boo[i].first + boo[i].second) / 2;
                f[mid[i]].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]);
            }

            ll amiri = 0;
            for(auto i : f[s]) {
                for(auto j : idx[i]) {
                    amiri += get(1, 1, m, j, j);
                    if(need[i] <= amiri) break;
                }
                if(amiri >= need[i]) {
                    ans[i] = mid[i];
                    boo[i].second = mid[i]-1;
                } else {
                    boo[i].first = mid[i]+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