oj.uz

Submission #25366

# Submission time Handle Problem Language Result Execution time Memory
25366 2017-06-21T11:54:10 Z dotorya Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 112596 KB 
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
static unsigned char str[55555555], *p = str;

class Node {
public:
	ll mn, v;
	bool chk;
	Node() {
		*this = Node(0, 0, false);
	}
	Node(ll mn, ll v, bool chk) : mn(mn), v(v), chk(chk) {}
};

class Segtree {
public:
	Node indt[1100000];
	Segtree() {
		memset(indt, 0, sizeof(indt));
	}
	void propagate(int n) {
		if (indt[n].chk) {
			indt[2 * n].mn = indt[n].v;
			indt[2 * n].v = indt[n].v;
			indt[2 * n].chk = true;
			indt[2 * n + 1].mn = indt[n].v;
			indt[2 * n + 1].v = indt[n].v;
			indt[2 * n + 1].chk = true;
			indt[n].chk = false;
		}
	}
	void update(int st, int en, int S, int E, int n, ll v) {
		if (st > en) return;
		if (st == S && en == E) {
			indt[n].mn = v;
			indt[n].v = v;
			indt[n].chk = true;
			return;
		}
		propagate(n);

		int M = (S + E) / 2;
		update(st, min(en, M), S, M, 2 * n, v);
		update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
		indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn);
	}
	ll getmn(int st, int en, int S, int E, int n) {
		if (st > en) return LL_INF;
		if (st == S && en == E) return indt[n].mn;
		propagate(n);

		int M = (S + E) / 2;
		return min(getmn(st, min(en, M), S, M, 2 * n), getmn(max(M + 1, st), en, M + 1, E, 2 * n + 1));
	}
};

Segtree st1, st2;
vector <ll> Vx;
ll in[100050][4];
int main() {
	fread(str, 1, 55555555, stdin);
	int M, N, i, j;
	rf(M) rf(N)
	//scanf("%d %d", &M, &N);
	for (i = 1; i <= M; i++) {
		rf(in[i][0]) rf(in[i][1]) rf(in[i][2]) rf(in[i][3])
		//scanf("%lld %lld %lld %lld", &in[i][0], &in[i][1], &in[i][2], &in[i][3]);
		Vx.push_back(in[i][2]);
	}
	Vx.push_back(1);
	Vx.push_back(N);
	sort(all(Vx));
	Vx.erase(unique(all(Vx)), Vx.end());

	st1.update(2, Vx.size(), 1, IT_MAX, 1, LL_INF);
	st2.update(1, Vx.size() - 1, 1, IT_MAX, 1, LL_INF);
	ll ans = LL_INF;
	for (i = 1; i <= M; i++) {
		int p1 = lower_bound(all(Vx), in[i][0]) - Vx.begin() + 1;
		int p2 = lower_bound(all(Vx), in[i][1] + 1) - Vx.begin();
		int p3 = lower_bound(all(Vx), in[i][2]) - Vx.begin() + 1;
		ll v = in[i][3];
		ans = min(ans, st1.getmn(p1, p1, 1, IT_MAX, 1) + st2.getmn(p2, p2, 1, IT_MAX, 1) + v);

		ll v1 = v + st1.getmn(p1, p3, 1, IT_MAX, 1);
		{
			int st = 1, en = p3, mi, rv = p3 + 1;
			while (st <= en) {
				mi = (st + en) / 2;
				if (st1.getmn(mi, mi, 1, IT_MAX, 1) > v1) {
					rv = mi;
					en = mi - 1;
				}
				else st = mi + 1;
			}
			st1.update(rv, p3, 1, IT_MAX, 1, v1);
		}
		ll v2 = v + st2.getmn(p3, p2, 1, IT_MAX, 1);
		{
			int st = p3, en = Vx.size(), mi, rv = p3 - 1;
			while (st <= en) {
				mi = (st + en) / 2;
				if (st2.getmn(mi, mi, 1, IT_MAX, 1) > v2) {
					rv = mi;
					st = mi + 1;
				}
				else en = mi - 1;
			}
			st2.update(p3, rv, 1, IT_MAX, 1, v2);
		}
	}
	if (ans == LL_INF) ans = -1;
	return !printf("%lld\n", ans);
}

Compilation message

pinball.cpp:24:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
pinball.cpp:25:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
pinball.cpp: In function 'int main()':
pinball.cpp:112:15: warning: unused variable 'j' [-Wunused-variable]
  int M, N, i, j;
               ^
pinball.cpp:111:32: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 55555555, stdin);
                                ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 110976 KB Output is correct
2 Correct 16 ms 110976 KB Output is correct
3 Correct 26 ms 110976 KB Output is correct
4 Correct 16 ms 110976 KB Output is correct
5 Correct 13 ms 110976 KB Output is correct
6 Correct 13 ms 110976 KB Output is correct
7 Correct 16 ms 110976 KB Output is correct
8 Correct 13 ms 110976 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 110976 KB Output is correct
2 Correct 16 ms 110976 KB Output is correct
3 Correct 16 ms 110976 KB Output is correct
4 Correct 16 ms 110976 KB Output is correct
5 Correct 9 ms 110976 KB Output is correct
6 Correct 9 ms 110976 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 110976 KB Output is correct
2 Correct 16 ms 110976 KB Output is correct
3 Correct 19 ms 110976 KB Output is correct
4 Correct 19 ms 110976 KB Output is correct
5 Correct 16 ms 110976 KB Output is correct
6 Correct 19 ms 110976 KB Output is correct
7 Correct 13 ms 110976 KB Output is correct
8 Correct 23 ms 110976 KB Output is correct
9 Correct 23 ms 110976 KB Output is correct
10 Correct 29 ms 110976 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 111248 KB Output is correct
2 Correct 179 ms 111444 KB Output is correct
3 Correct 763 ms 112596 KB Output is correct
4 Correct 456 ms 112596 KB Output is correct
5 Correct 529 ms 111828 KB Output is correct
6 Correct 716 ms 112596 KB Output is correct
7 Execution timed out 1000 ms 112596 KB Execution timed out
8 Halted 0 ms 0 KB -