Submission #1255598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255598		onbert	Festival (IOI25_festival)	C++20	100 / 100	85 ms	21932 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct thing {
    int p, t, id;
    bool operator < (const thing &b) const {
        if (t == b.t) return p < b.p;
        return (b.t - 1) * t * p < (t - 1) * b.t * b.p;
    }
};
const int maxn = 2e5 + 5, INF = 1e16;
int n;
vector<thing> a = {{0, 1, -1}}, A;

int first1;
int l[maxn], r[maxn];
int val[maxn], add1 = 0;
vector<int> pos[5];

void calc(int i) {
    if (val[l[i]] == INF) val[i] = INF;
    else val[i] = (val[l[i]] - A[i].p) * A[i].t;
    val[i] = min(val[i], INF);
}
int money(int i) {
    return val[i] + (i >= first1) * add1;
}
void update(int ll, int rr) {
    for (int i = ll; i <= rr; i = r[i]) {
        if (i >= first1) {
            int ori = val[i];
            calc(i);
            add1 = val[i] - ori;
            val[i] = ori;
            break;
        }
        calc(i);
    }
}

vector<int32_t> max_coupons(int32_t AA, vector<int32_t> P, vector<int32_t> T) {
    n = P.size();
    for (int i=0;i<n;i++) a.push_back({P[i], T[i], i});
    sort(a.begin() + 1, a.end());
    first1 = n+1;
    for (int i=1;i<=n;i++) if (a[i].t == 1) {
        first1 = i;
        break;
    }

    A = a;
    for (int i=1;i<=n;i++) l[i] = i-1, r[i] = i+1;
    val[0] = AA;

    pair<int, pair<int,int>> mxsz = {0, {0, 0}};
    int cursz = 0;
    vector<int> del;
    for (int i=1;i<=n;i++) {
        calc(i);
        pos[A[i].t].push_back(i);
        cursz++;
        while (money(i) < 0) {
            pair<int,int> mx = {-1, -1};
            for (int j=2;j<=4;j++) if (pos[j].size()) {
                int cur = pos[j].back();
                thing temp = A[cur];
                A[cur] = {0, 1, -1};
                update(cur, i);
                mx = max(make_pair(money(i), j), mx);
                A[cur] = temp;
                update(cur, i);
            }
            if (mx.first < 0) break;
            int J = mx.second;
            int cur = pos[J].back();
            pos[J].pop_back();
            A[cur] = {0, 1, -1};
            update(cur, i);
            del.push_back(cur);
            cursz--;
            r[l[cur]] = r[cur], l[r[cur]] = l[cur];
        }
        if (money(i) < 0) break;
        mxsz = max(make_pair(cursz, make_pair(i, (int)del.size())), mxsz);
    }

    vector<int32_t> ans;
    
    for (int i=0;i<mxsz.second.second;i++) a[del[i]].id = -1;
    for (int i=1;i<=mxsz.second.first;i++) if (a[i].id != -1) ans.push_back(a[i].id);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 27 / 27
• Subtask 6: 16 / 16
• Subtask 7: 18 / 18