#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 l, int r, int cl, int cr, ll u) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (l == cl && r == cr) {rez[x].lval = u; refresh(x);}
else if (r <= cmid) updatel(rez[x].l, l, r, cl, cmid, u);
else if (l > cmid) updatel(rez[x].r, l, r, cmid+1, cr, u);
else {
updatel(rez[x].l, l, cmid, cl, cmid, u);
updatel(rez[x].r, cmid+1, r, cmid+1, cr, u);
}
}
void updater(int x, int l, int r, int cl, int cr, ll u) {
if (cl != cr) push(x);
int cmid = (cl+cr)/2;
if (l == cl && r == cr) {rez[x].rval = u; refresh(x);}
else if (r <= cmid) updater(rez[x].l, l, r, cl, cmid, u);
else if (l > cmid) updater(rez[x].r, l, r, cmid+1, cr, u);
else {
updater(rez[x].l, l, cmid, cl, cmid, u);
updater(rez[x].r, cmid+1, r, 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, 0, maxn, 0);
updater(root, N-1, 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], C[i], 0, maxn, a+D[i]);
}
if (b != -1) {
updater(root, C[i], 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 |
Incorrect |
0 ms |
378584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
378584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
378584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
378584 KB |
Output is correct |
| 2 |
Correct |
139 ms |
378584 KB |
Output is correct |
| 3 |
Correct |
533 ms |
378584 KB |
Output is correct |
| 4 |
Incorrect |
403 ms |
378584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
