| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25365 |
2017-06-21T11:52:06 Z |
dotorya |
Pinball (JOI14_pinball) |
C++14 |
|
1000 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, 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: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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
56724 KB |
Output is correct |
| 2 |
Correct |
16 ms |
56724 KB |
Output is correct |
| 3 |
Correct |
9 ms |
56724 KB |
Output is correct |
| 4 |
Correct |
16 ms |
56724 KB |
Output is correct |
| 5 |
Correct |
16 ms |
56724 KB |
Output is correct |
| 6 |
Correct |
19 ms |
56724 KB |
Output is correct |
| 7 |
Correct |
13 ms |
56724 KB |
Output is correct |
| 8 |
Correct |
16 ms |
56724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
56724 KB |
Output is correct |
| 2 |
Correct |
26 ms |
56724 KB |
Output is correct |
| 3 |
Correct |
19 ms |
56724 KB |
Output is correct |
| 4 |
Correct |
13 ms |
56724 KB |
Output is correct |
| 5 |
Correct |
26 ms |
56724 KB |
Output is correct |
| 6 |
Correct |
16 ms |
56724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
56724 KB |
Output is correct |
| 2 |
Correct |
16 ms |
56724 KB |
Output is correct |
| 3 |
Correct |
29 ms |
56724 KB |
Output is correct |
| 4 |
Correct |
23 ms |
56724 KB |
Output is correct |
| 5 |
Correct |
26 ms |
56724 KB |
Output is correct |
| 6 |
Correct |
26 ms |
56724 KB |
Output is correct |
| 7 |
Correct |
23 ms |
56724 KB |
Output is correct |
| 8 |
Correct |
16 ms |
56724 KB |
Output is correct |
| 9 |
Correct |
19 ms |
56724 KB |
Output is correct |
| 10 |
Correct |
33 ms |
56724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
56996 KB |
Output is correct |
| 2 |
Correct |
263 ms |
57192 KB |
Output is correct |
| 3 |
Correct |
843 ms |
58344 KB |
Output is correct |
| 4 |
Correct |
476 ms |
58344 KB |
Output is correct |
| 5 |
Correct |
539 ms |
57576 KB |
Output is correct |
| 6 |
Correct |
749 ms |
58344 KB |
Output is correct |
| 7 |
Execution timed out |
1000 ms |
58344 KB |
Execution timed out |
| 8 |
Halted |
0 ms |
0 KB |
- |
