oj.uz

Submission #823409

# Submission time Handle Problem Language Result Execution time Memory
823409 2023-08-12T13:30:04 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
15 / 100
 474 ms 102400 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
const int64_t inf = 1e18;
#define pi pair<int64_t,int64_t>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()

#define int int64_t
const int sz=1<<30;
struct sgt {
	sgt *L, *R; int s;
	sgt() {
		L=R=NULL; s=inf;
	}
	void set(int l, int r, int i, int x) {
		if (r-l==1) {
			s=x; return;
		}
		int m=(l+r)>>1;
		if (i<m) {
			if (!L) L=new sgt();
			L->set(l,m,i,x);
		} else {
			if (!R) R=new sgt();
			R->set(m,r,i,x);
		}
		s = min(L?L->s:inf, R?R->s:inf);
	}
	void set(int i, int x) {
		set(0,sz,i,x);
	}
	int query(int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return inf;
		if (lx<=l && r<=rx) return s;
		int m=(l+r)>>1;
		int lq=L?L->query(l,m,lx,rx):inf;
		int rq=R?R->query(m,r,lx,rx):inf;
		return min(lq,rq);
	}
	int query(int l, int r) {
		return query(0,sz,l,r);
	}
};
#undef int

long long min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
	int n=x.size(), m=l.size();
	
	#define int int64_t

	sgt bottom, top;
	bottom.set(0,0);
	top.set(0,0);
	vector<vector<int>> add(n), del(n);
	del[0].pb(0);
	add[n-1].pb(0);
	forn(i,m) {
		add[l[i]].pb(y[i]);
		del[r[i]].pb(y[i]);
	}
	forn(i,n) {
		vector<pi> toset;
		for(auto&y:add[i]) {
			int f = bottom.query(0,y+1);
			int s = top.query(y,h[i]+1);
			if (min(f,s)==inf) continue;
			f+=y; s-=y;
			int x=min(f,s);
			toset.pb({y,x});
		}
		for(auto&y:del[i]) {
			bottom.set(y,inf);
			top.set(y,inf);
		}
		for(auto&x:toset) {
			bottom.set(x.f,x.s-x.f);
			top.set(x.f,x.s+x.f);
		}
	}
	if (top.s==inf) return -1;
	int64_t a = x[n-1];
	int64_t b = x[0];
	a-=b;
	int f = top.s+a;
	return f;

	#undef int
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3708 KB Output is correct
2 Correct 402 ms 94412 KB Output is correct
3 Correct 374 ms 80648 KB Output is correct
4 Correct 458 ms 99392 KB Output is correct
5 Correct 474 ms 100184 KB Output is correct
6 Correct 453 ms 102400 KB Output is correct
7 Correct 188 ms 55792 KB Output is correct
8 Correct 325 ms 93968 KB Output is correct
9 Correct 449 ms 98360 KB Output is correct
10 Correct 130 ms 19380 KB Output is correct
11 Correct 8 ms 3412 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3708 KB Output is correct
2 Correct 402 ms 94412 KB Output is correct
3 Correct 374 ms 80648 KB Output is correct
4 Correct 458 ms 99392 KB Output is correct
5 Correct 474 ms 100184 KB Output is correct
6 Correct 453 ms 102400 KB Output is correct
7 Correct 188 ms 55792 KB Output is correct
8 Correct 325 ms 93968 KB Output is correct
9 Correct 449 ms 98360 KB Output is correct
10 Correct 130 ms 19380 KB Output is correct
11 Correct 8 ms 3412 KB Output is correct
12 Correct 386 ms 88436 KB Output is correct
13 Correct 342 ms 95824 KB Output is correct
14 Correct 449 ms 94780 KB Output is correct
15 Correct 244 ms 45768 KB Output is correct
16 Correct 244 ms 44964 KB Output is correct
17 Correct 269 ms 44968 KB Output is correct
18 Correct 274 ms 45692 KB Output is correct
19 Correct 246 ms 44944 KB Output is correct
20 Correct 199 ms 54940 KB Output is correct
21 Correct 21 ms 7884 KB Output is correct
22 Correct 214 ms 74856 KB Output is correct
23 Correct 229 ms 76200 KB Output is correct
24 Correct 225 ms 81992 KB Output is correct
25 Correct 257 ms 86036 KB Output is correct
26 Correct 219 ms 94144 KB Output is correct
27 Correct 455 ms 95604 KB Output is correct
28 Correct 330 ms 99380 KB Output is correct
29 Correct 473 ms 93888 KB Output is correct
30 Correct 214 ms 55868 KB Output is correct
31 Correct 461 ms 98500 KB Output is correct
32 Correct 123 ms 15796 KB Output is correct
33 Incorrect 128 ms 17260 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -