Submission #707015

#	Time	Username	Problem	Language	Result	Execution time	Memory
707015		someone	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	267 ms	83252 KiB

constellation3

#include <bits/stdc++.h>
#define int long long
#define a second
#define b first
using namespace std;

struct Star {
    int x, y, c, val;
    
    bool operator <(const Star& other) const{
        if(y == other.y)
            return x < other.x;
        return y < other.y;
    }
};

struct Ans {
    set<Star> sup;
    int add = 0, minInf = 0;
    
    void upd(int h) {
        while(!sup.empty()) {
            auto it = sup.begin();
            if((*it).y > h) return;
            minInf = min(minInf, add + (*it).val);
            sup.erase(it);
        }
    }
    
    void merge(Ans other, int h) {
        other.upd(h);
        if((int)sup.size() < (int)other.sup.size()) {
            swap(add, other.add);
            swap(sup, other.sup);
            swap(minInf, other.minInf);
        }
        add += other.minInf;
        other.add += minInf;
        minInf += other.minInf;
        for(Star s : other.sup) {
            s.val += other.add - add;
            sup.insert(s);
        }
    }
    
    void print() {
        cout << add << ' ' << minInf << '\n';
        for(Star s : sup)
            cout << s.x << ' ' << s.y << ' ' << s.val << '\n';
        cout << '\n';
    }
};

const int N = 2e5 + 42, INF = 1e18 + 42;

vector<Star> stars[N];
int n, m, h[N], l[N], r[N];

Ans solve(int i) {
    if(i == -1) {
        Ans ans;
        return ans;
    }
    Ans ans;
    for(Star s : stars[i]) {
        ans.add += s.c;
        ans.sup.insert(s);
    }
    ans.minInf = ans.add;
    
    ans.merge(solve(l[i]), h[i]);
    ans.merge(solve(r[i]), h[i]);
    
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> h[i];
    cin >> m;
    for(int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        x--;
        stars[x].push_back({x, y, c, -c});
    }
    
    int maxi = 0;
    deque<int> imax;
    for(int i = 0; i < n; i++) {
        l[i] = -1;
        while(!imax.empty() && h[imax[0]] < h[i]) {
            l[i] = imax[0];
            imax.pop_front();
        }
        if(h[i] > h[maxi])
            maxi = i;
        imax.push_front(i);
    }
    imax.clear();
    for(int i = n-1; i > -1; i--) {
        r[i] = -1;
        while(!imax.empty() && h[imax[0]] <= h[i]) {
            r[i] = imax[0];
            imax.pop_front();
        }
        imax.push_front(i);
    }
    
    Ans ans = solve(maxi);
    ans.upd(INF);
    cout << ans.minInf;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65