oj.uz

Submission #823412

# Submission time Handle Problem Language Result Execution time Memory
823412 2023-08-12T13:34:16 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
15 / 100
 455 ms 102420 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 = 8e18;
#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 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 3668 KB Output is correct
2 Correct 382 ms 94516 KB Output is correct
3 Correct 437 ms 80700 KB Output is correct
4 Correct 427 ms 99300 KB Output is correct
5 Correct 454 ms 100188 KB Output is correct
6 Correct 446 ms 102420 KB Output is correct
7 Correct 179 ms 55884 KB Output is correct
8 Correct 329 ms 94136 KB Output is correct
9 Correct 445 ms 98332 KB Output is correct
10 Correct 129 ms 19420 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 3668 KB Output is correct
2 Correct 382 ms 94516 KB Output is correct
3 Correct 437 ms 80700 KB Output is correct
4 Correct 427 ms 99300 KB Output is correct
5 Correct 454 ms 100188 KB Output is correct
6 Correct 446 ms 102420 KB Output is correct
7 Correct 179 ms 55884 KB Output is correct
8 Correct 329 ms 94136 KB Output is correct
9 Correct 445 ms 98332 KB Output is correct
10 Correct 129 ms 19420 KB Output is correct
11 Correct 9 ms 3516 KB Output is correct
12 Correct 386 ms 88492 KB Output is correct
13 Correct 333 ms 95908 KB Output is correct
14 Correct 449 ms 94836 KB Output is correct
15 Correct 238 ms 45764 KB Output is correct
16 Correct 249 ms 44992 KB Output is correct
17 Correct 263 ms 44924 KB Output is correct
18 Correct 256 ms 45900 KB Output is correct
19 Correct 247 ms 44876 KB Output is correct
20 Correct 192 ms 54972 KB Output is correct
21 Correct 21 ms 7872 KB Output is correct
22 Correct 232 ms 74864 KB Output is correct
23 Correct 217 ms 76172 KB Output is correct
24 Correct 226 ms 82152 KB Output is correct
25 Correct 248 ms 86084 KB Output is correct
26 Correct 222 ms 94120 KB Output is correct
27 Correct 437 ms 95556 KB Output is correct
28 Correct 339 ms 99324 KB Output is correct
29 Correct 454 ms 93788 KB Output is correct
30 Correct 186 ms 55868 KB Output is correct
31 Correct 455 ms 98416 KB Output is correct
32 Correct 129 ms 15876 KB Output is correct
33 Incorrect 131 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 -