Submission #313040

#	Time	Username	Problem	Language	Result	Execution time	Memory
313040		limabeans	Pinball (JOI14_pinball)	C++17	100 / 100	308 ms	25964 KiB

pinball

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxm = 1e5 + 10;
const int maxn = 1e6 + 10;

const ll inf = 1e18;

template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return min(x, y);
    }
    int n;
    vector<T> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.assign(n*4, inf);
    }

    void upd(int v, int tl, int tr, int i, T dx) {
	if (tl == tr) {
	    t[v] = merge(t[v], dx);
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,dx);
	    } else {
		upd(2*v+1,tm+1,tr,i,dx);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return inf;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};


int m, n;

int a[maxm], b[maxm], c[maxm], d[maxm];

segtree<ll> dpL, dpR;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>m>>n;

    vector<int> ord;
    ord.push_back(0);
    ord.push_back(1);
    ord.push_back(n);
    
    for (int i=1; i<=m; i++) {
	cin>>a[i]>>b[i]>>c[i]>>d[i];
	ord.push_back(a[i]);
	ord.push_back(b[i]);
	ord.push_back(c[i]);
    }

    sort(ord.begin(),ord.end());
    ord.erase(unique(ord.begin(),ord.end()),ord.end());

    for (int i=1; i<=m; i++) {
	a[i] = std::lower_bound(ord.begin(),ord.end(),a[i])-ord.begin();
	b[i] = std::lower_bound(ord.begin(),ord.end(),b[i])-ord.begin();
	c[i] = std::lower_bound(ord.begin(),ord.end(),c[i])-ord.begin();
    }

    int N = (int)ord.size() - 1;

    dpL.init(N);
    dpR.init(N);

    ll ans = inf;

    for (int i=1; i<=m; i++) {
	int l = a[i];
	int r = b[i];

	ll left = (l==1 ? 0: dpL.qry(1,1,N,l,r)) + d[i];
	ll right = (r==N ? 0: dpR.qry(1,1,N,l,r)) + d[i];

	//cout<<left<<" "<<right<<endl;

	dpL.upd(1,1,N,c[i],left);
	dpR.upd(1,1,N,c[i],right);
	
	ans = min(ans, left+right-d[i]);
    }

    if (ans > inf/2) ans = -1;
    cout<<ans<<endl;
    
    
    return 0;
}

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