oj.uz

Submission #934948

# Submission time Handle Problem Language Result Execution time Memory
934948 2024-02-28T08:37:29 Z vjudge1 Pinball (JOI14_pinball) C++17
100 / 100
 372 ms 29724 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <array>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);

ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}

ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}

ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}

ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}

ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}

ll Ceil(ll a , ll b)
{
 if(b < 0)
  a *= -1, b *= -1;

 if(a < 0)return a/b;

 return(a + (b-1))/b;
}

/////////////////////
//VALS
const int maxn = 1e5;
const int INF = (1 << 19);
int lft[maxn + 10];
int rgt[maxn + 10];
int mid[maxn + 10];
int cost[maxn + 10];
ll dp[maxn + 10][2];
ll tri[2 * INF];
map<int, int>con;

/////////////////////
//FUNS
void reset() {
	for(int i = 0; i < 2 * INF; i++) {
		tri[i] = 1e18;
	}
}
void upd(int v, ll x) {
	v += INF;
	while(v > 0) {
		tri[v] = min(tri[v], x);
		v /= 2;
	}
}
ll que(int l, int r) {
	l += INF;
	r += INF;
	ll ans = 1e18;
	while(l <= r) {
		if(l & 1) {
			ans = min(ans, tri[l]);
		}
		if(!(r & 1)) {
			ans = min(ans, tri[r]);
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
/////////////////////
//SOLVE
void solve()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> lft[i] >> rgt[i] >> mid[i] >> cost[i];
		con[lft[i]] = 0;
		con[rgt[i]] = 0;
		con[mid[i]] = 0;
	}
	con[1] = 0;
	con[m] = 0;
	int k = 1;
	for(auto x : con) {
		con[x.F] = k++;
	}
	reset();
	upd(1, 0);
	for(int i = 1; i <= n; i++) {
		dp[i][0] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][0]);
	}
	reset();
	upd(con.size(), 0);
	for(int i = 1; i <= n; i++) {
		dp[i][1] = que(con[lft[i]], con[rgt[i]]) + cost[i];
		upd(con[mid[i]], dp[i][1]);
	}
	ll ans = 1e18;
	for(int i = 1; i <= n; i++) {
		//cout << dp[i][0] << ' ' << dp[i][1] << '\n';
		ans = min(ans, dp[i][0] + dp[i][1] - cost[i]);
	}
	if(ans == 1e18) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}

}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10708 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10708 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10708 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10708 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10932 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10708 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10708 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10932 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10716 KB Output is correct
17 Correct 4 ms 10844 KB Output is correct
18 Correct 5 ms 10720 KB Output is correct
19 Correct 5 ms 11100 KB Output is correct
20 Correct 3 ms 10844 KB Output is correct
21 Correct 3 ms 10844 KB Output is correct
22 Correct 4 ms 10844 KB Output is correct
23 Correct 4 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10708 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10708 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 4 ms 10844 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10932 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10716 KB Output is correct
17 Correct 4 ms 10844 KB Output is correct
18 Correct 5 ms 10720 KB Output is correct
19 Correct 5 ms 11100 KB Output is correct
20 Correct 3 ms 10844 KB Output is correct
21 Correct 3 ms 10844 KB Output is correct
22 Correct 4 ms 10844 KB Output is correct
23 Correct 4 ms 10844 KB Output is correct
24 Correct 5 ms 10844 KB Output is correct
25 Correct 21 ms 11868 KB Output is correct
26 Correct 58 ms 14428 KB Output is correct
27 Correct 169 ms 18736 KB Output is correct
28 Correct 99 ms 15644 KB Output is correct
29 Correct 122 ms 17436 KB Output is correct
30 Correct 163 ms 16468 KB Output is correct
31 Correct 290 ms 23636 KB Output is correct
32 Correct 271 ms 21336 KB Output is correct
33 Correct 33 ms 14420 KB Output is correct
34 Correct 134 ms 20240 KB Output is correct
35 Correct 165 ms 29500 KB Output is correct
36 Correct 372 ms 29524 KB Output is correct
37 Correct 309 ms 29720 KB Output is correct
38 Correct 301 ms 29724 KB Output is correct