Submission #710174

#	Time	Username	Problem	Language	Result	Execution time	Memory
710174		PixelCat	Reconstruction Project (JOI22_reconstruction)	C++14	7 / 100	328 ms	28708 KiB

reconstruction

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

mt19937_64 rng(48763);

struct Treap {
    Treap *l, *r;
    int pri;
    int key, size, sum;
    Treap(int _k) {
        l = r = nullptr;
        pri = rng();
        key = sum = _k;
        size = 1;
    }
};

int size(Treap *&rt) {
    if(rt) return rt->size;
    return 0;
}
int sum(Treap *&rt) {
    if(rt) return rt->sum;
    return 0;
}

void pull(Treap *&rt) {
    rt->size = size(rt->l) + size(rt->r) + 1;
    rt->sum = sum(rt->l) + sum(rt->r) + rt->key;
}

Treap* merge(Treap *a, Treap *b) {
    if(!a) return b;
    if(!b) return a;
    if(a->pri > b->pri) {
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

// a: key <= k
void split_key(Treap *rt, Treap *&a, Treap *&b, int k) {
    if(!rt) {
        a = b = nullptr;
        return;
    }
    if(rt->key <= k) {
        a = rt;
        split_key(rt->r, a->r, b, k);
        pull(a);
    } else {
        b = rt;
        split_key(rt->l, a, b->l, k);
        pull(b);
    }
}

// a: size = k
void split_size(Treap *rt, Treap *&a, Treap *&b, int k) {
    if(!rt) {
        a = b = nullptr;
        return;
    }
    if(size(rt->l) + 1 <= k) {
        a = rt;
        split_key(rt->r, a->r, b, k - size(rt->l) - 1);
        pull(a);
    } else {
        b = rt;
        split_key(rt->l, a, b->l, k);
        pull(b);
    }
}

void insert(Treap *&rt, int x) {
    Treap *a, *b;
    split_key(rt, a, b, x);
    rt = merge(a, merge(new Treap(x), b));
}
void erase(Treap *&rt, int x) {
    Treap *a, *b, *c;
    split_key(rt, a, b, x - 1);
    split_size(b, b, c, 1);
    delete b;
    rt = merge(a, c);
}

int eval(Treap *&rt, int x) {
    Treap *a, *b;
    split_key(rt, a, b, x);
    int res = x * (size(a) - size(b)) - sum(a) + sum(b);
    rt = merge(a, b);
    return res;
}

struct Nyan {
    int ssm, sbg;
    multiset<int> sm, bg;
    int last_qry;
    void init() {
        ssm = sbg = 0;
        sm.clear();
        bg.clear();
        last_qry = 0;
    }
    void insert(int x) {
        if(x <= last_qry) {
            sm.insert(x);
            ssm += x;
        } else {
            bg.insert(x);
            sbg += x;
        }
    }
    void erase(int x) {
        if(x <= last_qry) {
            sm.erase(sm.find(x));
            ssm -= x;
        } else {
            bg.erase(bg.find(x));
            sbg -= x;
        }
    }
    int eval(int x) {
        while(sz(bg) && (*bg.begin()) <= x) {
            int k = *bg.begin();
            ssm += k;
            sbg -= k;
            sm.insert(k);
            bg.erase(bg.begin());
        }
        last_qry = x;
        return x * (sz(sm) - sz(bg)) - ssm + sbg;
    }
} owo;

const int MAXN = 510;

vector<int> v[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, m; cin >> n >> m;
    For(i, 1, m) {
        int a, b, w; cin >> a >> b >> w;
        assert(b == a + 1);
        v[a].eb(w);
    }
    vector<pair<int, pii>> ev;  // {time, {old, new}}
    // Treap *rt = nullptr;
    owo.init();
    For(i, 1, n - 1) {
        sort(all(v[i]));
        // insert(rt, v[i][0]);
        owo.insert(v[i][0]);
        For(j, 1, sz(v[i]) - 1) {
            int a = v[i][j - 1];
            int b = v[i][j];
            int mi = b - ((b - a) / 2);
            ev.eb(mi, pii(a, b));
        }
    }
    sort(all(ev));
    reverse(all(ev));
    int q; cin >> q;
    while(q--) {
        int x; cin >> x;
        while(sz(ev) && ev.back().F <= x) {
            auto p = ev.back().S;
            // erase(rt, p.F);
            // insert(rt, p.S);
            owo.erase(p.F);
            owo.insert(p.S);
            ev.pop_back();
        }
        // cout << eval(rt, x) << "\n";
        cout << owo.eval(x) << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 7 / 7
• Subtask 4: 0 / 28
• Subtask 5: 0 / 35
• Subtask 6: 0 / 23