Submission #519991

#	Time	Username	Problem	Language	Result	Execution time	Memory
519991		amunduzbaev	Pinball (JOI14_pinball)	C++14	100 / 100	230 ms	31704 KiB

pinball

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 3e5 + 5;

struct ST{
	int tree[N<<2];
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = min(tree[x], v); return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return 1e15;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}pref, suff;


signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	vector<ar<int, 4>> a(n);
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (a[i][0] < a[j][0]);
	});
	
	int r = 1;
	for(auto i : p){
		if(r < a[i][0]){
			cout<<-1<<"\n"; return 0;
		} r = max(r, a[i][1]);
	} if(r < m) { cout<<-1<<"\n"; return 0; }
	
	vector<ar<int, 2>> pp;
	for(int i=0;i<n;i++){
		pp.push_back({i, 0});
		pp.push_back({i, 1});
		pp.push_back({i, 2});
	}
	
	sort(pp.begin(), pp.end(), [&](auto& i, auto& j){
		return (a[i[0]][i[1]] < a[j[0]][j[1]]);
	});
	int last = 0;
	for(int i=0;i<n*3;){ int j = i;
		while(j < n*3 && a[pp[i][0]][pp[i][1]] == a[pp[j][0]][pp[j][1]]) j++;
		while(i < j){
			a[pp[i][0]][pp[i][1]] = last;
			i++;
		} last++;
	}
	
	memset(pref.tree, 127, sizeof pref.tree);
	memset(suff.tree, 127, sizeof suff.tree);
	int res = 1e15;
	for(int i=0;i<n;i++){
		int l = a[i][0], r = a[i][1], c = a[i][2], d = a[i][3];
		int pp = pref.get(l, r);
		if(l == 0) pp = 0;
		pref.sett(c, pp + d);
		
		int ss = suff.get(l, r);
		if(r == last - 1) ss = 0;
		suff.sett(c, ss + d);
		res = min(res, pp + ss + d);
	}
	
	if(res == 1e15) cout<<-1<<"\n";
	else cout<<res<<"\n";
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49