Submission #25365

#	Time	Username	Problem	Language	Result	Execution time	Memory
25365		dotorya	Pinball (JOI14_pinball)	C++14	51 / 100	1000 ms	58344 KiB

pinball

#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>  

#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;

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() {
	int M, N, i, j;
	scanf("%d %d", &M, &N);
	for (i = 1; i <= M; i++) {
		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 (stderr)

pinball.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
pinball.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
pinball.cpp: In function 'int main()':
pinball.cpp:109:15: warning: unused variable 'j' [-Wunused-variable]
  int M, N, i, j;
               ^
pinball.cpp:110:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N);
                        ^
pinball.cpp:112:75: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld %lld", &in[i][0], &in[i][1], &in[i][2], &in[i][3]);
                                                                           ^

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49