oj.uz

Submission #25367

# Submission time Handle Problem Language Result Execution time Memory
25367 2017-06-21T11:57:43 Z dotorya Pinball (JOI14_pinball) C++14
100 / 100
 436 ms 58344 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>  

#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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