oj.uz

Submission #6970

# Submission time Handle Problem Language Result Execution time Memory
6970 2014-07-12T00:27:10 Z model_code Pinball (JOI14_pinball) C++
100 / 100
 288 ms 22468 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); i++)
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pr(x) cout << #x << " = " << x << endl

typedef long long llint;
typedef vector<int> vint;
typedef vector<llint> vllint;

const llint INFLL = 1001001001001001001ll;

int in() {
	int a;
	scanf("%d", &a);
	return a;
}

int M, N;
vint coords;

int c2i(int x) {
	vint::iterator iter = lower_bound(all(coords), x);
	if (*iter == x) {
		return iter - coords.begin();
	}
	
	cerr << "Fatal error: compression failed." << endl;
	exit(-1);
	return -1;
}

struct Device {
	int a, b, c;
	llint d;
	void compress() {
		a = c2i(a);
		b = c2i(b);
		c = c2i(c);
	}
} dev[100010];

struct RMQ {
	int n;
	vllint data;
	
	RMQ(int n)
		: n(n), data(n * 2) {
		rep(i, n * 2) data[i] = INFLL;
	}
	
	llint query(int a, int b, int k, int l, int r) {
		if (b <= l || r <= a) return INFLL;
		if (a <= l && r <= b) return data[k];
		return min(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	
	void update(int i, llint x) {
		i += n - 1;
		data[i] = x;
		while (i > 0) {
			i = (i - 1) / 2;
			data[i] = min(data[i * 2 + 1], data[i * 2 + 2]);
		}
	}
	
	llint value(int i) {
		return data[i + n - 1];
	}
	
	bool chmin(int i, llint x) {
		if (x < value(i)) {
			update(i, x);
			return true;
		}
		else {
			return false;
		}
	}
};

int main() {
	M = in();
	N = in();
	rep(i,M) {
		dev[i].a = in() - 1;
		dev[i].b = in();
		dev[i].c = in() - 1;
		dev[i].d = in();
		
		coords.pb(dev[i].a);
		coords.pb(dev[i].b);
		coords.pb(dev[i].c);
	};
	
	coords.pb(0);
	coords.pb(N);
	sort(all(coords));
	coords.erase(unique(all(coords)), coords.end());
	N = coords.size();
	rep(i,M) dev[i].compress();
	
	int n = 1;
	while(n < N) n *= 2;
	RMQ lq(n), rq(n);
	
	llint ans = INFLL;
	
	rep(i,M) {
		llint costl = (dev[i].a == 0 ? 0 : lq.query(dev[i].a, dev[i].b, 0, 0, n)) + dev[i].d;
		llint costr = (dev[i].b == N - 1 ? 0 : rq.query(dev[i].a, dev[i].b, 0, 0, n)) + dev[i].d;
		
		lq.chmin(dev[i].c, costl);
		rq.chmin(dev[i].c, costr);
		
		llint cost = costl + costr - dev[i].d;
		if (cost < ans) ans = cost;
	}
	
	cout << (ans == INFLL ? -1 : ans) << endl;
	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4024 KB Output is correct
2 Correct 0 ms 4024 KB Output is correct
3 Correct 0 ms 4024 KB Output is correct
4 Correct 0 ms 4024 KB Output is correct
5 Correct 0 ms 4024 KB Output is correct
6 Correct 0 ms 4024 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4024 KB Output is correct
2 Correct 0 ms 4024 KB Output is correct
3 Correct 0 ms 4024 KB Output is correct
4 Correct 0 ms 4024 KB Output is correct
5 Correct 0 ms 4184 KB Output is correct
6 Correct 0 ms 4024 KB Output is correct
7 Correct 0 ms 4024 KB Output is correct
8 Correct 0 ms 4184 KB Output is correct
9 Correct 0 ms 4184 KB Output is correct
10 Correct 0 ms 4184 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4676 KB Output is correct
2 Correct 56 ms 6596 KB Output is correct
3 Correct 160 ms 9156 KB Output is correct
4 Correct 152 ms 7100 KB Output is correct
5 Correct 120 ms 9156 KB Output is correct
6 Correct 192 ms 7100 KB Output is correct
7 Correct 248 ms 10180 KB Output is correct
8 Correct 220 ms 10180 KB Output is correct
9 Correct 32 ms 6340 KB Output is correct
10 Correct 108 ms 13252 KB Output is correct
11 Correct 184 ms 22468 KB Output is correct
12 Correct 288 ms 22468 KB Output is correct
13 Correct 240 ms 22468 KB Output is correct
14 Correct 220 ms 22468 KB Output is correct