Submission #1292440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292440		1ota	Topical (NOI23_topical)	C++20	40 / 100	1078 ms	211800 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

const int inf = 9e18;

struct SegTree{
    int n; pii identity = {-inf, -inf};
    vector<pii> Tree;
    function<pii(pii&, pii&)> combine = [](pii& a, pii& b) { return max(a, b); };

    SegTree (int n) : n(n) {
        Tree.resize(4 * n, identity);
    }

    void build (vector<pii>& arr, int idx, int l, int r){
        if (l == r) { Tree[idx] = arr[l]; return; }
        int mid = (l + r) / 2;
        build(arr, 2 * idx + 1, l, mid);
        build(arr, 2 * idx + 2, mid+1, r);
        Tree[idx] = combine(Tree[2 * idx + 1], Tree[2 * idx + 2]);
    }

    void build(vector<pii>& arr){
        build(arr, 0, 0, n-1);
    }

    void update (int i, int delta, int idx, int l, int r){
        if (l == r and i == l) {Tree[idx].ff += delta; return; }
        if (i < l or r < i) return;
        int mid = (l + r) / 2;
        update(i, delta, 2 * idx + 1, l, mid);
        update(i, delta, 2 * idx + 2, mid+1, r);
        Tree[idx] = combine(Tree[2 * idx + 1], Tree[2 * idx + 2]);
    }

    void update (int i, int delta){
        update(i, delta, 0, 0, n-1);
    }

    pii query (int ql, int qr, int idx, int l, int r){
        if (r < ql or qr < l) return identity;
        if (ql <= l and r <= qr) return Tree[idx];
        int mid = (l + r) / 2;
        pii v1 = query(ql, qr, 2 * idx + 1, l, mid);
        pii v2 = query(ql, qr, 2 * idx + 2, mid+1, r);
        return combine(v1, v2);
    }

    pii query (){
        return query(0, n-1, 0, 0, n-1);
    }
};

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, k; cin >> n >> k;

    vector<vector<int>> a(n, vector<int>(k, 0)), b(n, vector<int>(k, 0));
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> a[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) cin >> b[i][j];

    vector<vector<pii>> t(k, vector<pii>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) t[j][i] = pii{a[i][j], i};
    for (int i = 0; i < k; i++) sort(entire(t[i]));

    int ans = 0;
    vector<int> c(n, 0), idx(k, 0), cur(k, 0);

    SegTree lesson(n);
    vector<pii> initialState(n);
    for (int i = 0; i < n; i++){
        auto& [ci, ind] = initialState[i];
        ci = 0; ind = i;
    } lesson.build(initialState);


    auto update = [&](){
        for (int i = 0; i < k; i++){
            while (idx[i] < n and t[i][idx[i]].ff <= cur[i]) lesson.update(t[i][idx[i]].ss, 1), idx[i]++;
        }
    };

    auto add = [&](){
        auto [ci, i] = lesson.query();
        if (ci == k){
            lesson.update(i, -inf);
            for (int j = 0; j < k; j++) cur[j] += b[i][j];
            return true;
        }
        return false;
    };

    for (int i = 0; i < n; i++){
        update();
        if (!add()) break;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 28 / 28
• Subtask 3: 0 / 21
• Subtask 4: 0 / 39