#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#define debug(...) 42
//#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int offset = 1e6 + 5;
const int off = (1<<21);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
int t[off<<1];
int unit = 0;
int get(int idx){
int mx = t[idx+=off];
while (idx/=2)
ckmax(mx, t[idx]);
return mx;
}
void update(int l, int r, int v, int idx=1, int lo=0, int hi=off){
if (r <= lo || hi <= l)
return;
if (l <= lo && hi <= r){
t[idx] = v;
return;
}
int mi = (lo+hi)>>1;
update(l, r, v, ls, lo, mi);
update(l, r, v, rs, mi, hi);
return;
}
} seg;
int dp[MAXN][2];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int x, y, n;
cin >> x >> y >> n;
y += offset;
vector<pair<pii, pii>> a(n + 1);
vector<array<int, 3>> lines(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i].F.F >> a[i].F.S >> a[i].S.F >> a[i].S.S;
a[i].F.S += offset;
a[i].S.S += offset;
if (a[i].F.F > a[i].S.F) swap(a[i].F.F, a[i].S.F);
if (a[i].F.S < a[i].S.S) swap(a[i].F.S, a[i].S.S);
lines[i] = {a[i].S.F + 1, a[i].F.S + 1, a[i].S.S - 1}; // x axis, up, down
}
lines.pb({x, y, y});
sort(1 + all(lines), [](array<int, 3> lhs, array<int, 3> rhs){
if (lhs[0] != rhs[0]) return lhs[0] < rhs[0];
return lhs[2] < rhs[2];
});
for (int i = 1; i <= n + 1; i++){
int up = seg.get(lines[i][1]);
int dw = seg.get(lines[i][2]);
if (up == 0){
dp[i][0] = lines[i][0] + abs(offset - lines[i][1]);
} else {
dp[i][0] = lines[i][0] - lines[up][0] + min(abs(lines[up][1] - lines[i][1]) + dp[up][0], abs(lines[up][2] - lines[i][1]) + dp[up][1]);
}
if (dw == 0){
dp[i][1] = lines[i][0] + abs(100 - lines[i][2]);
} else {
dp[i][1] = lines[i][0] - lines[dw][0] + min(abs(lines[dw][1] - lines[i][2]) + dp[dw][0], abs(lines[dw][2] - lines[i][2]) + dp[dw][1]);
}
seg.update(lines[i][2], lines[i][1] + 1, i);
if (lines[i][0] == x && lines[i][1] == y){
cout << min(dp[i][0], dp[i][1]) << endl;
}
debug(i, dp[i][0], dp[i][1], lines[i], up, dw);
}
cout << 0 << endl;
debug(a);
debug(lines);
}
Compilation message
walk.cpp: In function 'int main()':
walk.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define debug(...) 42
| ^~
walk.cpp:89:3: note: in expansion of macro 'debug'
89 | debug(i, dp[i][0], dp[i][1], lines[i], up, dw);
| ^~~~~
walk.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define debug(...) 42
| ^~
walk.cpp:92:2: note: in expansion of macro 'debug'
92 | debug(a);
| ^~~~~
walk.cpp:7:20: warning: statement has no effect [-Wunused-value]
7 | #define debug(...) 42
| ^~
walk.cpp:93:2: note: in expansion of macro 'debug'
93 | debug(lines);
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Found length 93, official output says 89. |
| 2 |
Incorrect |
0 ms |
348 KB |
Found length 1602, official output says 1190. |
| 3 |
Incorrect |
1 ms |
860 KB |
Found length 164592, official output says 160150. |
| 4 |
Incorrect |
1 ms |
860 KB |
Found length 126794, official output says 126772. |
| 5 |
Incorrect |
37 ms |
3864 KB |
Found length 175585, official output says 175579. |
| 6 |
Partially correct |
14 ms |
2036 KB |
Partially correct (80% score). Path ends at the wrong point. |
| 7 |
Incorrect |
23 ms |
2436 KB |
Found length 109351, official output says 109253. |
| 8 |
Incorrect |
50 ms |
4188 KB |
Found length 16351, official output says 16349. |
| 9 |
Incorrect |
39 ms |
4188 KB |
Found length 287623, official output says 217249. |
| 10 |
Incorrect |
40 ms |
4184 KB |
Found length 196675, official output says 196657. |
