oj.uz

Submission #709570

# Submission time Handle Problem Language Result Execution time Memory
709570 2023-03-13T23:37:41 Z GusterGoose27 Treatment Project (JOI20_treatment) C++17
35 / 100
 146 ms 26100 KB 
#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);
	}
	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]);
	}
	assert(!snodes.empty());
	while (!pq.empty()) {
		pli tp = pq.top();
		pq.pop();
		if (tp.first > dist[tp.second]) continue;
		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';
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 26060 KB Output is correct
2 Correct 139 ms 26100 KB Output is correct
3 Runtime error 38 ms 10364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 7 ms 1748 KB Output is correct
21 Correct 7 ms 1748 KB Output is correct
22 Correct 7 ms 1816 KB Output is correct
23 Correct 6 ms 1752 KB Output is correct
24 Correct 8 ms 1944 KB Output is correct
25 Correct 8 ms 1748 KB Output is correct
26 Correct 7 ms 1748 KB Output is correct
27 Correct 6 ms 1748 KB Output is correct
28 Correct 10 ms 1872 KB Output is correct
29 Correct 10 ms 1748 KB Output is correct
30 Correct 5 ms 1752 KB Output is correct
31 Correct 4 ms 1736 KB Output is correct
32 Correct 9 ms 2004 KB Output is correct
33 Correct 9 ms 2008 KB Output is correct
34 Correct 7 ms 1748 KB Output is correct
35 Correct 8 ms 2004 KB Output is correct
36 Correct 9 ms 1972 KB Output is correct
37 Correct 7 ms 1756 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 26060 KB Output is correct
2 Correct 139 ms 26100 KB Output is correct
3 Runtime error 38 ms 10364 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -