#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, int> pli;
const int MAXN = 1e5;
const int inf = 1e6;
int t, n;
pii points[2*MAXN];
int cost[MAXN];
vector<int> snodes;
vector<int> enodes;
int xsort[2*MAXN];
int ysort[2*MAXN];
int xinv[2*MAXN];
int yinv[2*MAXN];
ll dist[2*MAXN];
struct compx {
bool operator()(int a, int b) {
pii compa = pii(-points[a].first, points[a].second);
pii compb = pii(-points[b].first, points[b].second);
return compa == compb ? (b & 1) : compa < compb;
}
} compx;
struct compy {
bool operator()(int a, int b) {
pii compa = pii(points[a].second, -points[a].first);
pii compb = pii(points[b].second, -points[b].first);
return compa == compb ? (b & 1) : compa < compb;
}
} compy;
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
int mn; // min by y
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp < rp) {
int mid = (lp+rp)/2;
l = new stree(lp, mid);
r = new stree(mid+1, rp);
mn = min(l->mn, r->mn);
}
else mn = yinv[xsort[lp]];
}
int get_mn(int lv, int rv) { // returns position of element in ysort/2
if (lp > rv || rp < lv) return inf;
if (lp >= lv && rp <= rv) return mn;
return min(l->get_mn(lv, rv), r->get_mn(lv, rv));
}
void del(int p) { // position of element in xsort
if (lp > p || rp < p) return;
if (lp == rp) {
mn = inf;
return;
}
l->del(p);
r->del(p);
mn = min(l->mn, r->mn);
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> t >> n;
for (int i = 0; i < n; i++) {
int x, y1, y2;
cin >> x >> y1 >> y2 >> cost[i];
if (y1 == 1) snodes.push_back(i);
if (y2 == t) enodes.push_back(i);
points[2*i] = pii(x-y1, x+y1);
points[2*i+1] = pii(x-y2-1, x+y2+1);
}
while (points[6].second&1) n++;
iota(xsort, xsort+2*n, 0);
iota(ysort, ysort+2*n, 0);
sort(xsort, xsort+2*n, compx);
sort(ysort, ysort+2*n, compy);
for (int i = 0; i < 2*n; i++) {
xinv[xsort[i]] = i;
yinv[ysort[i]] = i;
}
priority_queue<pli, vector<pli>, greater<pli>> pq;
stree *tree = new stree(0, 2*n-1);
fill(dist, dist+2*n, -1);
for (int v: snodes) {
dist[v] = cost[v];
pq.push(pli(cost[v], v));
tree->del(xinv[2*v]);
tree->del(xinv[2*v+1]);
}
while (!pq.empty()) {
pli tp = pq.top();
pq.pop();
int xpos = xinv[2*tp.second+1]-1;
int ypos = yinv[2*tp.second+1]-1;
int curv;
while ((curv = tree->get_mn(0, xpos)) <= ypos) {
curv = ysort[curv];
curv /= 2;
tree->del(xinv[2*curv]);
tree->del(xinv[2*curv+1]);
dist[curv] = dist[tp.second]+cost[curv];
pq.push(pli(dist[curv], curv));
}
}
ll ans = -1;
for (int v: enodes) {
if ((dist[v] != -1) && (ans == -1 || dist[v] < ans)) ans = dist[v];
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
25744 KB |
Output is correct |
| 2 |
Correct |
113 ms |
25724 KB |
Output is correct |
| 3 |
Execution timed out |
3073 ms |
2516 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
3072 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Execution timed out |
3072 ms |
212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
135 ms |
25744 KB |
Output is correct |
| 2 |
Correct |
113 ms |
25724 KB |
Output is correct |
| 3 |
Execution timed out |
3073 ms |
2516 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
