oj.uz

Submission #525112

# Submission time Handle Problem Language Result Execution time Memory
525112 2022-02-10T17:53:20 Z orientor Pinball (JOI14_pinball) C++17
100 / 100
 943 ms 104280 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 448 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 448 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 5 ms 1092 KB Output is correct
20 Correct 4 ms 564 KB Output is correct
21 Correct 2 ms 820 KB Output is correct
22 Correct 4 ms 1328 KB Output is correct
23 Correct 4 ms 1356 KB Output is correct
24 Correct 4 ms 1368 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 448 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 4 ms 716 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 5 ms 1092 KB Output is correct
20 Correct 4 ms 564 KB Output is correct
21 Correct 2 ms 820 KB Output is correct
22 Correct 4 ms 1328 KB Output is correct
23 Correct 4 ms 1356 KB Output is correct
24 Correct 4 ms 1368 KB Output is correct
25 Correct 43 ms 5312 KB Output is correct
26 Correct 141 ms 18228 KB Output is correct
27 Correct 427 ms 30780 KB Output is correct
28 Correct 233 ms 6000 KB Output is correct
29 Correct 307 ms 28644 KB Output is correct
30 Correct 348 ms 9744 KB Output is correct
31 Correct 747 ms 51924 KB Output is correct
32 Correct 660 ms 36552 KB Output is correct
33 Correct 85 ms 20196 KB Output is correct
34 Correct 362 ms 52276 KB Output is correct
35 Correct 435 ms 103864 KB Output is correct
36 Correct 943 ms 104256 KB Output is correct
37 Correct 764 ms 104212 KB Output is correct
38 Correct 688 ms 104280 KB Output is correct