Submission #525112

#	Time	Username	Problem	Language	Result	Execution time	Memory
525112		orientor	Pinball (JOI14_pinball)	C++17	100 / 100	943 ms	104280 KiB

pinball

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ld long double
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]

// Uncomment when using kactl templates and change typedef of pair
// #define rep(i, a, b) for(int i = a; i < (b); ++i)
// #define sz(x) (int)(x).size()
// typedef pair<int, int> pii;

typedef vector< int > vi;
typedef vector<long long> lvi;
typedef vector< vector<int> > vvi;
typedef vector< vector<long long> > lvvi;
typedef pair< int,int > ii;
typedef pair< long long,long long > lii;
typedef vector<pair<int,int>> vii;
typedef vector<pair<long long,long long>> lvii;
typedef vector<vector<pair<int,int>>> vvii;
typedef vector<vector<pair<long long,long long>>> lvvii;
typedef vector<bool> vb;

mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
// usage: x = rng() % k; shuffle(all(v), rng);

#define all(c) (c).begin(),(c).end()
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define pb push_back
#define ss second
#ifdef ONLINE_JUDGE
    #define error(args...) 0
#else
    #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#endif
void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr <<"[ "<< *it << " = " << a << " ]";
    err(++it, args...);
}

//-----------------------------------------------------------------------------------------------------------------------------------------------------------------
const long long mod = 1e9 + 7;
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

long long mos() { return 0LL; }
template<typename T, typename... Args>
T mos(T a, Args... args) { return ((a + mos(args...))%mod + mod)%mod; }

long long mop() { return 1LL; }
template<typename T, typename... Args>
T mop(T a, Args... args) { return (a*mop(args...))%mod; }
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

const ll INF = 1e16;

class SegmentTrees {
	lvi st;
public:
	SegmentTrees(int n) {
		st.assign(4*n, INF);
	}
	void update(int idx,ll val,int left,int right,int pos=1) {
		if(left == right) st[pos] = min(st[pos], val);
		else {
			int mid = (left + right) /2 ;
			if(idx <= mid) update(idx, val, left, mid, pos*2);
			else update(idx, val, mid + 1, right, pos*2 + 1);
			st[pos] = min(st[pos*2], st[pos*2 + 1]);
		}
	}
	ll query(int l,int r,int left,int right,int pos=1) {
		if(l > r) return INF;
		if(l == left and r == right) return st[pos];
		else {
			int mid = (left + right) /2; 
			return min(query(l, min(r, mid), left, mid, pos*2), query(max(l, mid + 1), r, mid + 1, right, pos*2 + 1));
		}
	}
};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    
    int m, n;
    cin >> m >> n;
    vi A(m), B(m), C(m), D(m);
    map<int,int> mp;
    auto add = [&](int x) {
    	if(x < 0 or x >= n) return;
    	mp[x];
    };
    for(int i = 0; i < m; i++) {
    	cin >> A[i] >> B[i] >> C[i] >> D[i];
    	A[i]--; B[i]--; C[i]--;
    	for(int delta = -1; delta <= 1; delta++) {
    		add(A[i] + delta);
    		add(B[i] + delta);
    		add(C[i] + delta);
    	}
    }
    int N = 0;
    for(auto &[key, val] : mp) val = N++;
    error(N);
    for(int i = 0; i < m; i++) {
    	A[i] = mp[A[i]];
    	B[i] = mp[B[i]];
    	C[i] = mp[C[i]];
    	// error(A[i], B[i], C[i]);
    }
    SegmentTrees sgtp(N), sgts(N);
    sgtp.update(0, 0, 0, N - 1);
    sgts.update(N - 1, 0, 0, N - 1);
    ll ans = INF;
    for(int i = 0; i < m; i++) {
    	// finish at this step.
    	ans = min(ans, D[i] +  sgtp.query(A[i], B[i], 0, N - 1) + sgts.query(A[i], B[i], 0, N - 1));

    	// update prefix
    	ll pmin = sgtp.query(A[i], C[i] - 1, 0, N - 1);
    	sgtp.update(C[i], pmin + D[i], 0, N - 1);

    	// update suffix
    	ll smin = sgts.query(C[i] + 1, B[i], 0, N - 1);
    	sgts.update(C[i], smin + D[i], 0, N - 1);
    	// error(i);
    	// for(int j = 0; j < N; j++) {
    	// 	cerr << sgtp.query(j, j, 0, N - 1) << " ";
    	// }
    	// cerr << endl;
    	// for(int j = 0; j < N; j++) {
    	// 	cerr << sgts.query(j, j, 0, N - 1) << " ";
    	// }
    	// cerr << endl;
    }
    if(ans >= INF) cout << -1 << endl;
    else
    cout << ans << endl;
    return 0;
}    


// WA
// 1. overflow
// 2. re-initialize global variables for every test case.
// 3. edge cases like n=1

// Run time error
// 1. division by zero.
// 2. array bounds.

// TLE
// 1. uncomment that #define endl '\n' line

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