oj.uz

Submission #380494

# Submission time Handle Problem Language Result Execution time Memory
380494 2021-03-22T04:51:49 Z pure_mem Pinball (JOI14_pinball) C++14
11 / 100
 395 ms 6380 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12, M = 1e9;
const ll INF = 1e18;

struct node{
	node *l, *r;
	ll val = INF;
};
int n, m, dp[N], p[N];
ll cL[N], cR[N];

void upd(node *v, int tl, int tr, int pos, ll val){
	if(tl > pos || pos > tr)
		return;
	if(tl == tr){
		v->val = min(v->val, val);
		return;	
	}
	int tm = (tl + tr) / 2;
	if(!v->l)
		v->l = new node();
	if(!v->r)
		v->r = new node();
	upd(v->l, tl, tm, pos, val);
	upd(v->r, tm + 1, tr, pos, val);
	v->val = min(v->l->val, v->r->val);
}
ll get(node *v, int tl, int tr, int l, int r){
	if(tl > r || l > tr || !v)
		return INF;
    if(tl >= l && tr <= r)
    	return v->val;
    int tm = (tl + tr) / 2;
    return min(get(v->l, tl, tm, l, r), get(v->r, tm + 1, tr, l, r));
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> m >> n;
	ll ans = INF;
	node* root1 = new node();
	node* root2 = new node();
	for(int i = 1;i <= n;i++){
		int l, r, c, cost;
		cin >> l >> r >> c >> cost;
		cL[i] = get(root1, 1, n, l, r) + cost;
		if(l == 1)
			cL[i] = cost;
		cR[i] = get(root2, 1, n, l, r) + cost;
		if(r == n)
			cR[i] = cost;
		ans = min(ans, cL[i] + cR[i] - cost);
		upd(root1, 1, n, c, cL[i]);
		upd(root2, 1, n, c, cR[i]);
	}
	if(ans == INF)
		ans = -1;
	cout << ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 287 ms 2796 KB Output is correct
10 Correct 202 ms 3052 KB Output is correct
11 Correct 395 ms 3060 KB Output is correct
12 Runtime error 251 ms 6380 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 287 ms 2796 KB Output is correct
10 Correct 202 ms 3052 KB Output is correct
11 Correct 395 ms 3060 KB Output is correct
12 Runtime error 251 ms 6380 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 287 ms 2796 KB Output is correct
10 Correct 202 ms 3052 KB Output is correct
11 Correct 395 ms 3060 KB Output is correct
12 Runtime error 251 ms 6380 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -