oj.uz

Submission #823407

# Submission time Handle Problem Language Result Execution time Memory
823407 2023-08-12T13:27:16 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
15 / 100
 473 ms 102380 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
using ll = long long;
const ll inf = 1e18;
#define pi pair<ll,ll>
#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

ll 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;
	ll a = x[n-1];
	ll 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 0 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 49 ms 3712 KB Output is correct
2 Correct 423 ms 94460 KB Output is correct
3 Correct 360 ms 80752 KB Output is correct
4 Correct 473 ms 99416 KB Output is correct
5 Correct 466 ms 100220 KB Output is correct
6 Correct 458 ms 102380 KB Output is correct
7 Correct 181 ms 55868 KB Output is correct
8 Correct 335 ms 94064 KB Output is correct
9 Correct 452 ms 98416 KB Output is correct
10 Correct 141 ms 19488 KB Output is correct
11 Correct 9 ms 3516 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3712 KB Output is correct
2 Correct 423 ms 94460 KB Output is correct
3 Correct 360 ms 80752 KB Output is correct
4 Correct 473 ms 99416 KB Output is correct
5 Correct 466 ms 100220 KB Output is correct
6 Correct 458 ms 102380 KB Output is correct
7 Correct 181 ms 55868 KB Output is correct
8 Correct 335 ms 94064 KB Output is correct
9 Correct 452 ms 98416 KB Output is correct
10 Correct 141 ms 19488 KB Output is correct
11 Correct 9 ms 3516 KB Output is correct
12 Correct 386 ms 88528 KB Output is correct
13 Correct 381 ms 95832 KB Output is correct
14 Correct 454 ms 94852 KB Output is correct
15 Correct 248 ms 45692 KB Output is correct
16 Correct 262 ms 44936 KB Output is correct
17 Correct 259 ms 44952 KB Output is correct
18 Correct 244 ms 45884 KB Output is correct
19 Correct 268 ms 44936 KB Output is correct
20 Correct 226 ms 54932 KB Output is correct
21 Correct 22 ms 7892 KB Output is correct
22 Correct 222 ms 74856 KB Output is correct
23 Correct 221 ms 76244 KB Output is correct
24 Correct 219 ms 82072 KB Output is correct
25 Correct 236 ms 85996 KB Output is correct
26 Correct 224 ms 94144 KB Output is correct
27 Correct 448 ms 95608 KB Output is correct
28 Correct 361 ms 99424 KB Output is correct
29 Correct 450 ms 93836 KB Output is correct
30 Correct 195 ms 55852 KB Output is correct
31 Correct 448 ms 98456 KB Output is correct
32 Correct 136 ms 15780 KB Output is correct
33 Incorrect 133 ms 17344 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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