Submission #1278171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278171		PlayVoltz	Pinball (JOI14_pinball)	C++20	100 / 100	372 ms	80872 KiB

pinball

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct ooga{
	int l, r, x, c;
};

struct node{
	int s, e, m, val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=LLONG_MAX/10;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int ind, int nv){
		if (s==e)val=min(nv, val);
		else{
			if (ind<=m)l->up(ind, nv);
			else r->up(ind, nv);
			val = min(l->val, r->val);
		}
	}
	int query(int left, int right){
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return min(l->query(left, m), r->query(m+1, right));
	}
}*stl, *str;

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, a, b, c, d, ans=LLONG_MAX/10;
	cin>>n>>m;
	vector<int> ord;
	ord.pb(1);
	ord.pb(m);
	vector<ooga> vect(n);
	for (int i=0; i<n; ++i)cin>>a>>b>>c>>d, vect[i]={a, b, c, d}, ord.pb(a), ord.pb(b), ord.pb(c);
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	for (int i=0; i<n; ++i){
		vect[i].l=lower_bound(ord.begin(), ord.end(), vect[i].l)-ord.begin();
		vect[i].r=lower_bound(ord.begin(), ord.end(), vect[i].r)-ord.begin();
		vect[i].x=lower_bound(ord.begin(), ord.end(), vect[i].x)-ord.begin();
	}
	stl = new node(0, ord.size()-1);
	str = new node(0, ord.size()-1);
	stl->up(0, 0);
	str->up(ord.size()-1, 0);
	for (auto c:vect){
		int left=stl->query(c.l, c.r), right=str->query(c.l, c.r);
		stl->up(c.x, left+c.c);
		str->up(c.x, right+c.c);
		ans=min(ans, left+right+c.c);
	}
	cout<<(ans==LLONG_MAX/10?-1:ans);
}

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