1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include <bits/stdc++.h>
using namespace std;
#define N 2010
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
int n, k;
int h[N];
int p[N], c[N], a[N], b[N], al[N], ar[N], bl[N], br[N];
int f[N][N];
int main() {
freopen("lantern.in", "r", stdin);
freopen("lantern.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", h + i);
vector<int> l(k), r(k);
for (int i = 1; i <= k; ++i) {
scanf("%d%d%d%d", p + i, c + i, a + i, b + i);
al[i] = p[i] + 1;
while (al[i] > 1 && h[al[i] - 1] >= a[i]) --al[i];
ar[i] = p[i] - 1;
while (ar[i] < n && h[ar[i] + 1] >= a[i]) ++ar[i];
bl[i] = p[i] + 1;
while (bl[i] > 1 && h[bl[i] - 1] <= b[i]) --bl[i];
br[i] = p[i] - 1;
while (br[i] < n && h[br[i] + 1] <= b[i]) ++br[i];
l[i - 1] = r[i - 1] = i;
}
memset(f, -1, sizeof(f));
sort(l.begin(), l.end(), [&](int x, int y){return mp(a[x], -b[x]) < mp(a[y], -b[y]);});
sort(r.begin(), r.end(), [&](int x, int y){return mp(b[x], -a[x]) > mp(b[y], -a[y]);});
priority_queue<pii, vector<pii>, greater<pii> > lz[N], rz[N];
for (auto i : l) {
for (auto j : r) {
if (a[i] < a[j] && b[j] < b[i]) {
f[i][j] = f[i][i];
} else if (a[j] < a[i] && b[i] < b[j]) {
f[i][j] = f[j][j];
} else if (a[i] <= a[j] && b[i] <= b[j]) {
int z = max(al[i], bl[j]), y = min(ar[i], br[j]);
if (p[i] < z || p[i] > y || p[j] < z || p[j] > y) continue;
if (z == 1 && y == n) {
f[i][j] = 0;
goto nxt;
}
while (!lz[i].empty() && (p[lz[i].top().se] < z || p[lz[i].top().se] > y || a[lz[i].top().se] > b[j])) lz[i].pop();
if (!lz[i].empty()) {
f[i][j] = lz[i].top().fi;
}
while (!rz[j].empty() && (p[rz[j].top().se] < z || p[rz[j].top().se] > y || b[rz[j].top().se] < a[i])) rz[j].pop();
if (!rz[j].empty()) {
(f[i][j] == -1 || f[i][j] > rz[j].top().fi) && (f[i][j] = rz[j].top().fi);
}
}
nxt:
if (~f[i][j]) {
lz[i].emplace(f[i][j] + c[j], j);
rz[j].emplace(f[i][j] + c[i], i);
}
}
}
for (int i = 1; i <= k; ++i) {
printf("%d\n", f[i][i] == -1 ? f[i][i] : f[i][i] + c[i]);
}
return 0;
}
|
