Submission #1307113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307113		vincentbucourt1	새로운 문제 (POI11_met)	C++20	24 / 100	153 ms	131072 KiB

met

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

const int OO = (int)1e18;

int numStates, numSectors;
vector<int> sectorState; // sectorState[sector] = state
vector<vector<int>> stateSectors; // stateSectors[state] = {sectors}
vector<int> stateNeed; // stateNeed[state] = sum
int Q;

struct Node {
    int sum = 0;
    int childL = OO, childR = OO;
    int interL, interR;
    bool includes (int iSector) {
        return (interL <= iSector && iSector <= interR);
    }
};
struct SegPers {
    int numleaves;
    vector<Node> nodes;
    vector<int> iRoot; // iRoot[time] = idx of root
    SegPers (int n) {
        numleaves = 1;
        while (numleaves < n) numleaves *= 2;
        nodes.resize(2*numleaves-1);
        nodes[0].interL = 0, nodes[0].interR = numleaves-1;
        for (int i = 0; i < (int)nodes.size(); i++) {
            nodes[i].childL = 2*(i+1) - 1;
            nodes[i].childR = 2*(i+1);
            if (2*(i+1) < (int)nodes.size()) {
                int childL = nodes[i].childL, childR = nodes[i].childR;
                int mid = (nodes[i].interL + nodes[i].interR) / 2;
                nodes[childL].interL = nodes[i].interL;
                nodes[childL].interR = mid;
                nodes[childR].interL = mid+1;
                nodes[childR].interR = nodes[i].interR;
            }
        }
        for (int i = 0; i < (int)nodes.size(); i++) {
            if (nodes[i].interL == nodes[i].interR) {
                nodes[i].childL = OO;
                nodes[i].childR = OO;
            }
        }
        iRoot.emplace_back(0);
        // cerr << "SEGTREE INIT:\n";
        // for (int i = 0; i < (int)nodes.size(); i++) cerr << nodes[i].interL << " " << nodes[i].interR << "\n";
        // cerr << "------------------------\n";
    }
    void increment (Node node, int idx, int val) {
        bool changeL = false, changeR = false;
        if (node.childL < (int)nodes.size() && nodes[node.childL].includes(idx)) {
            increment(nodes[node.childL], idx, val);
            changeL = true;
        }
        else if (node.childR < (int)nodes.size() && nodes[node.childR].includes(idx)) {
            increment(nodes[node.childR], idx, val);
            changeR = true;
        }
        nodes.emplace_back(Node{
            node.sum + val,
            (changeL ? (int)nodes.size()-1 : node.childL),
            (changeR ? (int)nodes.size()-1 : node.childR),
            node.interL,
            node.interR
        });
        // cerr << "["  << node.interL << ", " << node.interR << "]: " << node.sum + val << "\n";
    }
    void increment (int idx, int val) {
        increment(nodes[iRoot.back()], idx, val);
        iRoot.emplace_back((int)nodes.size() - 1);
    }
    int query (int qL, int qR, int time) {
        Node node = nodes[iRoot[time]];
        return query(node, qL, qR);
    }
    int query (Node node, int qL, int qR) {
        int nL = node.interL, nR = node.interR;
        if (qL <= nL && nR <= qR) {
            return node.sum;
        }
        else if (qR < nL || nR < qL) {
            return 0;
        }
        else {
            return query(nodes[node.childL], qL, qR) + query(nodes[node.childR], qL, qR);
        }
    }
};

signed main() {
    fastIO();
    cin >> numStates >> numSectors;
    sectorState.resize(numSectors);
    stateSectors.resize(numStates);
    stateNeed.resize(numStates);
    for (int iSector = 0; iSector < numSectors; iSector++) {
        cin >> sectorState[iSector];
        sectorState[iSector]--;
        stateSectors[sectorState[iSector]].emplace_back(iSector);
    }
    for (int iState = 0; iState < numStates; iState++) {
        cin >> stateNeed[iState];
    } 
    cin >> Q;
    SegPers segtree(numSectors+1);
    for (int iQuery = 0; iQuery < Q; iQuery++) {
        int l, r, cnt;
        cin >> l >> r >> cnt;
        l--, r--;
        if (l <= r) {
            segtree.increment(l, cnt);
            segtree.increment(r+1, -cnt);
            segtree.increment(0, 0);
            segtree.increment(0, 0);
        }
        else {
            assert(l > r);
            segtree.increment(0, cnt);
            segtree.increment(r+1, -cnt);
            segtree.increment(l, cnt);
            segtree.increment(numSectors, -cnt);
        }
        assert((int)segtree.nodes.size() <= 4*numSectors + (iQuery+1)*4*30);
    }
    for (int iState = 0; iState < numStates; iState++) {
        int loT = -1, hiT = Q; // T : queries in time [0, T]
        while (hiT - loT > 1) {
            int midT = loT + (hiT - loT) / 2;
            int sum = 0;
            for (int iSector : stateSectors[iState]) {
                sum += segtree.query(0, iSector, 4*(midT+1));
            }
            if (sum >= stateNeed[iState]) {
                hiT = midT;
            }
            else {
                loT = midT;
            }
        }
        if (hiT == Q) {
            cout << "NIE\n";
        }
        else {
            cout << hiT+1 << "\n";
        }
    }
}

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