Submission #358120

#	Time	Username	Problem	Language	Result	Execution time	Memory
358120		ijxjdjd	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	46 ms	23788 KiB

constellation3

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(2e5) + 5;
struct Seg {
    ll mx[4*MAXN];
    Seg() {
        memset(mx, 0, sizeof(mx));
    }
    void upd(int i, ll val, int n = 1, int tl = 0, int tr = MAXN-1) {
        if (tl == tr) {
            if (val == -1) {
                mx[n] = -1;
            }
            else {
                mx[n] = max(mx[n], val);
            }
        }
        else {
            int tm = (tl + tr)/2;
            if (i <= tm) {
                upd(i, val, 2*n, tl, tm);
            }
            else {
                upd(i, val, 2*n+1, tm+1, tr);
            }
            mx[n] = max(mx[2*n], mx[2*n+1]);
        }
    }
    ll get(int l, int r, int n = 1, int tl=0,int tr=MAXN-1) {
        if (l <= tl && tr <= r) {
            return mx[n];
        }
        else if (r < tl || l > tr) {
            return -1;
        }
        else {
            int tm = (tl + tr)/2;
            return max(get(l, r, 2*n, tl, tm), get(l, r, 2*n+1, tm+1, tr));
        }
    }
};
Seg byY;
Seg byX;
Seg heights;
int A[MAXN];
vector<pair<int, ll>> store[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	FR(i, N) cin >> A[i];
	int M;
	cin >> M;
	ll tot = 0;
	FR(i, M) {
	    int a, b, c;
	    cin >> a >> b >> c;
	    	    tot += c;
        a--;
        store[a].push_back({b, c});
	}
	FR(i, MAXN) {
        heights.upd(i, -1);
	}
	ll curMax = 0;
	FR(i, N) {
        curMax = max(curMax, byY.get(0, A[i]));
        for (auto point : store[i]) {
//            cout << heights.get(point.first, N) << endl;
            ll next = max(curMax, byX.get(0, heights.get(point.first, MAXN-1))) + point.second;
            byX.upd(i, next);
            byY.upd(point.first, curMax+point.second);
        }
        heights.upd(A[i], i);
	}
	cout << tot - byX.get(0, MAXN-1) << '\n';
	return 0;
}

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