Submission #1194221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194221		physics07	Nile (IOI24_nile)	C++20	32 / 100	99 ms	21692 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct pt {
    int w, c;
    bool operator<(const pt &P) const {
        return w < P.w;
    }
} a[100001];
struct foo {
    ll d, v, idx;
    bool operator<(const foo &P) const {
        return d < P.d;
    }
} b[100001];
struct query {
    int d, idx;
    bool operator<(const query &Q) const {
        return d < Q.d;
    }
};
struct Node {
    ll oo, ox, xo, xx;
    Node(ll _oo, ll _ox, ll _xo, ll _xx) : oo(_oo), ox(_ox), xo(_xo), xx(_xx) {}
    Node() {
        oo = ox = xo = xx = 0;
    }
    Node operator+(const Node &p) {
        return Node(max({ox+p.oo, oo+p.xo, ox+p.xo}), max({ox+p.ox, oo+p.xx, ox+p.xx}), max({xo+p.xo, xx+p.oo, xx+p.xo}), max({xo+p.xx, xx+p.ox, xx+p.xx}));
    }
};
struct segtree {
    Node tree[4 * 100001];
    void init() {
        for(int i=1; i<400004; i++) tree[i] = Node();
    }
    void update(int node, int s, int e, int idx, ll v) {
        if(s > idx || e < idx) return;
        if(s == e) {
            tree[node].oo = v;
            tree[node].ox = tree[node].xo = tree[node].xx = 0;
            return;
        }
        int mid = s + e >> 1;
        update(node * 2, s, mid, idx, v);
        update(node * 2 + 1, mid + 1, e, idx, v);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
} tree;
vector<query> v;
vector<ll> ans;
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int q = (int)E.size();
    int n = (int)W.size();
    for(int i=0; i<n; i++) a[i] = {W[i], A[i] - B[i]};
    sort(a, a+n);
    for(int i=1; i<n; i++) b[i] = {a[i].w - a[i-1].w, a[i].c + a[i-1].c, i};
    sort(b+1, b+n);
    ans.resize(q);
    ans[0] = 0;
    for(int i=0; i<n; i++) ans[0] += A[i];
    for(int i=0; i<q; i++) ans[i] = ans[0];
    for(int i=0; i<q; i++) v.push_back({E[i], i});
    sort(v.begin(), v.end());
    tree.init();
    int idx = 1;
    for(int i=0; i<q; i++) {
        for(; idx < n && v[i].d >= b[idx].d; idx++) tree.update(1, 1, n-1, b[idx].idx, b[idx].v);
        ans[v[i].idx] -= max({tree.tree[1].oo, tree.tree[1].ox, tree.tree[1].xo, tree.tree[1].xx});
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18