답안 #25367 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25367	2017-06-21T11:57:43 Z	dotorya	Pinball (JOI14_pinball)	C++14	100 / 100	436 ms	58344 KB

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, Vx.size(), 1, IT_MAX, 1) + st2.getmn(1, p2, 1, IT_MAX, 1) + v);

		ll v1 = v + st1.getmn(p1, Vx.size(), 1, IT_MAX, 1);
		if (st1.getmn(p3, p3, 1, IT_MAX, 1) > v1) st1.update(p3, p3, 1, IT_MAX, 1, v1);

		ll v2 = v + st2.getmn(1, p2, 1, IT_MAX, 1);
		if (st2.getmn(p3, p3, 1, IT_MAX, 1) > v2) st2.update(p3, p3, 1, IT_MAX, 1, v2);
	}
	if (ans == LL_INF) ans = -1;
	return !printf("%lld\n", ans);
}

Compilation message

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.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	56724 KB	Output is correct
2	Correct	16 ms	56724 KB	Output is correct
3	Correct	13 ms	56724 KB	Output is correct
4	Correct	16 ms	56724 KB	Output is correct
5	Correct	13 ms	56724 KB	Output is correct
6	Correct	19 ms	56724 KB	Output is correct
7	Correct	16 ms	56724 KB	Output is correct
8	Correct	9 ms	56724 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	56724 KB	Output is correct
2	Correct	13 ms	56724 KB	Output is correct
3	Correct	19 ms	56724 KB	Output is correct
4	Correct	19 ms	56724 KB	Output is correct
5	Correct	19 ms	56724 KB	Output is correct
6	Correct	9 ms	56724 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	56724 KB	Output is correct
2	Correct	16 ms	56724 KB	Output is correct
3	Correct	26 ms	56724 KB	Output is correct
4	Correct	19 ms	56724 KB	Output is correct
5	Correct	23 ms	56724 KB	Output is correct
6	Correct	23 ms	56724 KB	Output is correct
7	Correct	13 ms	56724 KB	Output is correct
8	Correct	26 ms	56724 KB	Output is correct
9	Correct	19 ms	56724 KB	Output is correct
10	Correct	26 ms	56724 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	56996 KB	Output is correct
2	Correct	106 ms	57192 KB	Output is correct
3	Correct	289 ms	58344 KB	Output is correct
4	Correct	236 ms	58344 KB	Output is correct
5	Correct	196 ms	57576 KB	Output is correct
6	Correct	326 ms	58344 KB	Output is correct
7	Correct	423 ms	58344 KB	Output is correct
8	Correct	409 ms	58344 KB	Output is correct
9	Correct	69 ms	57192 KB	Output is correct
10	Correct	166 ms	57576 KB	Output is correct
11	Correct	286 ms	58344 KB	Output is correct
12	Correct	436 ms	58344 KB	Output is correct
13	Correct	399 ms	58344 KB	Output is correct
14	Correct	373 ms	58344 KB	Output is correct

답안 #25367

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0