#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
const int maxn = 1073741823;
int M, N;
int A[100000], B[100000], C[100000], D[100000];
typedef struct Node_ {
int l, r, p;
ll lval, rval;
} Node;
Node rez[12000001];
int rezcnt = 1;
int root;
int createNode() {
rez[rezcnt].l = rez[rezcnt].r = rez[rezcnt].p = 0;
rez[rezcnt].lval = rez[rezcnt].rval = -1;
return rezcnt++;
}
void push(int x) {
int l = rez[x].l;
int r = rez[x].r;
if (!l) l = rez[x].l = createNode();
rez[l].p = x;
if (!r) r = rez[x].r = createNode();
rez[r].p = x;
}
void refresh(int x) {
x = rez[x].p;
int l = rez[x].l, r = rez[x].r;
if (!l) l = rez[x].l = createNode();
if (!r) r = rez[x].r = createNode();
while (x) {
ll a = rez[rez[x].l].lval, b = rez[rez[x].r].lval;
ll c = rez[rez[x].l].rval, d = rez[rez[x].r].rval;
if (a == -1) rez[x].lval = b;
else if (b == -1) rez[x].lval = a;
else rez[x].lval = min(a, b);
if (c == -1) rez[x].rval = d;
else if (d == -1) rez[x].rval = c;
else rez[x].rval = min(c, d);
x = rez[x].p;
}
}
ll lget(int x, int l, int r, int cl, int cr) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (l == cl && r == cr) return rez[x].lval;
else if (r <= cmid) return lget(rez[x].l, l, r, cl, cmid);
else if (l > cmid) return lget(rez[x].r, l, r, cmid+1, cr);
else {
ll a = lget(rez[x].l, l, cmid, cl, cmid);
ll b = lget(rez[x].r, cmid+1, r, cmid+1, cr);
if (a == -1) return b;
else if (b == -1) return a;
else return min(a, b);
}
}
ll rget(int x, int l, int r, int cl, int cr) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (l == cl && r == cr) return rez[x].rval;
else if (r <= cmid) return rget(rez[x].l, l, r, cl, cmid);
else if (l > cmid) return rget(rez[x].r, l, r, cmid+1, cr);
else {
ll a = rget(rez[x].l, l, cmid, cl, cmid);
ll b = rget(rez[x].r, cmid+1, r, cmid+1, cr);
if (a == -1) return b;
else if (b == -1) return a;
else return min(a, b);
}
}
void updatel(int x, int p, int cl, int cr, ll u) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (p == cl && p == cr) {
if (rez[x].lval == -1) rez[x].lval = u;
else rez[x].lval = min(rez[x].lval, u);
refresh(x);
}
else if (p <= cmid) updatel(rez[x].l, p, cl, cmid, u);
else if (p > cmid) updatel(rez[x].r, p, cmid+1, cr, u);
}
void updater(int x, int p, int cl, int cr, ll u) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (p == cl && p == cr) {
if (rez[x].rval == -1) rez[x].rval = u;
else rez[x].rval = min(rez[x].rval, u);
refresh(x);
}
else if (p <= cmid) updater(rez[x].l, p, cl, cmid, u);
else if (p > cmid) updater(rez[x].r, p, cmid+1, cr, u);
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
scanf("%d%d", &M, &N);
for (int i = 0; i < M; i++) {
scanf("%d%d%d%d", &(A[i]), &(B[i]), &(C[i]), &(D[i]));
A[i]--; B[i]--; C[i]--;
}
root = createNode();
updatel(root, 0, 0, maxn, 0);
updater(root, N-1, 0, maxn, 0);
ll ans = (ll)1e18;
for (int i = 0; i < M; i++) {
ll a = lget(root, A[i], B[i], 0, maxn);
ll b = rget(root, A[i], B[i], 0, maxn);
if (a != -1) {
updatel(root, C[i], 0, maxn, a+D[i]);
}
if (b != -1) {
updater(root, C[i], 0, maxn, b+D[i]);
}
if (a != -1 && b != -1) {
ans = min(ans, a+b+D[i]);
}
}
if (ans == (ll)1e18) puts("-1");
else printf("%lld\n", ans);
return 0;
}
Compilation message
pinball.cpp: In function 'int main(int, char**)':
pinball.cpp:112:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &M, &N);
^
pinball.cpp:114:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &(A[i]), &(B[i]), &(C[i]), &(D[i]));
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 2 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 3 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 5 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 6 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 7 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 8 |
Correct |
0 ms |
378584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 2 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 3 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 4 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 5 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 6 |
Correct |
0 ms |
378584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 2 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 3 |
Correct |
6 ms |
378584 KB |
Output is correct |
| 4 |
Correct |
3 ms |
378584 KB |
Output is correct |
| 5 |
Correct |
6 ms |
378584 KB |
Output is correct |
| 6 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 7 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 8 |
Correct |
0 ms |
378584 KB |
Output is correct |
| 9 |
Correct |
3 ms |
378584 KB |
Output is correct |
| 10 |
Correct |
3 ms |
378584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
378584 KB |
Output is correct |
| 2 |
Correct |
139 ms |
378584 KB |
Output is correct |
| 3 |
Correct |
529 ms |
378584 KB |
Output is correct |
| 4 |
Correct |
429 ms |
378584 KB |
Output is correct |
| 5 |
Correct |
363 ms |
378584 KB |
Output is correct |
| 6 |
Correct |
693 ms |
378584 KB |
Output is correct |
| 7 |
Correct |
843 ms |
378584 KB |
Output is correct |
| 8 |
Correct |
816 ms |
378584 KB |
Output is correct |
| 9 |
Correct |
56 ms |
378584 KB |
Output is correct |
| 10 |
Correct |
286 ms |
378584 KB |
Output is correct |
| 11 |
Correct |
313 ms |
378584 KB |
Output is correct |
| 12 |
Correct |
723 ms |
378584 KB |
Output is correct |
| 13 |
Correct |
513 ms |
378584 KB |
Output is correct |
| 14 |
Correct |
413 ms |
378584 KB |
Output is correct |
