oj.uz

Submission #823451

# Submission time Handle Problem Language Result Execution time Memory
823451 2023-08-12T14:21:32 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
33 / 100
 541 ms 109160 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 = int64_t;
const ll inf = 4e18;
#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 ll
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 ll

	sgt st;
	forn(i,n) st.set(i,-h[i]);

	sgt bottom, top;
	bottom.set(0,0);
	top.set(0,0);
	vector<vector<int>> del(n);
	vector<vector<pi>> add(n);
	del[0].pb(0);
	add[n-1].pb({0,inf});
	forn(i,m) {
		add[l[i]].pb({y[i],-st.query(l[i],r[i]+1)});
		del[r[i]].pb(y[i]);
	}
	forn(i,n) {
		vector<pi> toset;
		for(auto&it:add[i]) {
			int y=it.f, z=it.s;
			int f = bottom.query(0,y+1);
			int s = top.query(y,z+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;
	int f = top.s+x[n-1]-x[0];
	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 60 ms 4804 KB Output is correct
2 Correct 384 ms 95492 KB Output is correct
3 Correct 390 ms 82460 KB Output is correct
4 Correct 521 ms 106160 KB Output is correct
5 Correct 492 ms 107352 KB Output is correct
6 Correct 523 ms 109160 KB Output is correct
7 Correct 223 ms 62096 KB Output is correct
8 Correct 396 ms 100328 KB Output is correct
9 Correct 491 ms 104688 KB Output is correct
10 Correct 186 ms 26096 KB Output is correct
11 Correct 21 ms 6580 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4804 KB Output is correct
2 Correct 384 ms 95492 KB Output is correct
3 Correct 390 ms 82460 KB Output is correct
4 Correct 521 ms 106160 KB Output is correct
5 Correct 492 ms 107352 KB Output is correct
6 Correct 523 ms 109160 KB Output is correct
7 Correct 223 ms 62096 KB Output is correct
8 Correct 396 ms 100328 KB Output is correct
9 Correct 491 ms 104688 KB Output is correct
10 Correct 186 ms 26096 KB Output is correct
11 Correct 21 ms 6580 KB Output is correct
12 Correct 416 ms 90132 KB Output is correct
13 Correct 418 ms 102712 KB Output is correct
14 Correct 500 ms 101944 KB Output is correct
15 Correct 346 ms 52772 KB Output is correct
16 Correct 341 ms 51996 KB Output is correct
17 Correct 394 ms 51968 KB Output is correct
18 Correct 359 ms 52796 KB Output is correct
19 Correct 415 ms 51928 KB Output is correct
20 Correct 284 ms 61216 KB Output is correct
21 Correct 48 ms 14136 KB Output is correct
22 Correct 315 ms 81592 KB Output is correct
23 Correct 336 ms 83104 KB Output is correct
24 Correct 331 ms 88908 KB Output is correct
25 Correct 354 ms 92700 KB Output is correct
26 Correct 316 ms 100868 KB Output is correct
27 Correct 541 ms 102600 KB Output is correct
28 Correct 426 ms 106224 KB Output is correct
29 Correct 517 ms 100536 KB Output is correct
30 Correct 218 ms 62180 KB Output is correct
31 Correct 486 ms 104788 KB Output is correct
32 Correct 177 ms 21656 KB Output is correct
33 Correct 223 ms 23808 KB Output is correct
34 Correct 232 ms 26640 KB Output is correct
35 Correct 246 ms 39228 KB Output is correct
36 Correct 234 ms 35788 KB Output is correct
37 Correct 204 ms 17256 KB Output is correct
38 Correct 233 ms 21432 KB Output is correct
39 Correct 236 ms 29752 KB Output is correct
40 Correct 203 ms 21016 KB Output is correct
41 Correct 196 ms 18688 KB Output is correct

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 -