oj.uz

Submission #1014170

# Submission time Handle Problem Language Result Execution time Memory
1014170 2024-07-04T13:24:13 Z vjudge1 Walk (CEOI06_walk) C++17
80 / 100
 47 ms 4188 KB 
#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(offset - 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);
      |  ^~~~~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct (80% score). Path ends at the wrong point.
2 Partially correct 0 ms 348 KB Partially correct (80% score). Path ends at the wrong point.
3 Partially correct 0 ms 860 KB Partially correct (80% score). Path ends at the wrong point.
4 Partially correct 1 ms 860 KB Partially correct (80% score). Path ends at the wrong point.
5 Partially correct 37 ms 3856 KB Partially correct (80% score). Path ends at the wrong point.
6 Partially correct 14 ms 2036 KB Partially correct (80% score). Path ends at the wrong point.
7 Partially correct 26 ms 2396 KB Partially correct (80% score). Path ends at the wrong point.
8 Partially correct 47 ms 4188 KB Partially correct (80% score). Path ends at the wrong point.
9 Partially correct 40 ms 4188 KB Partially correct (80% score). Path ends at the wrong point.
10 Partially correct 40 ms 4184 KB Partially correct (80% score). Path ends at the wrong point.