oj.uz

Submission #823426

# Submission time Handle Problem Language Result Execution time Memory
823426 2023-08-12T13:59:51 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
15 / 100
 471 ms 102360 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 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

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 ll

	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]);
			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 51 ms 3712 KB Output is correct
2 Correct 387 ms 94476 KB Output is correct
3 Correct 409 ms 80768 KB Output is correct
4 Correct 431 ms 99276 KB Output is correct
5 Correct 459 ms 100324 KB Output is correct
6 Correct 469 ms 102360 KB Output is correct
7 Correct 185 ms 55876 KB Output is correct
8 Correct 332 ms 93992 KB Output is correct
9 Correct 449 ms 98460 KB Output is correct
10 Correct 136 ms 19436 KB Output is correct
11 Correct 10 ms 3412 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3712 KB Output is correct
2 Correct 387 ms 94476 KB Output is correct
3 Correct 409 ms 80768 KB Output is correct
4 Correct 431 ms 99276 KB Output is correct
5 Correct 459 ms 100324 KB Output is correct
6 Correct 469 ms 102360 KB Output is correct
7 Correct 185 ms 55876 KB Output is correct
8 Correct 332 ms 93992 KB Output is correct
9 Correct 449 ms 98460 KB Output is correct
10 Correct 136 ms 19436 KB Output is correct
11 Correct 10 ms 3412 KB Output is correct
12 Correct 379 ms 88420 KB Output is correct
13 Correct 341 ms 95852 KB Output is correct
14 Correct 451 ms 94860 KB Output is correct
15 Correct 242 ms 45772 KB Output is correct
16 Correct 251 ms 44936 KB Output is correct
17 Correct 267 ms 44980 KB Output is correct
18 Correct 238 ms 45752 KB Output is correct
19 Correct 252 ms 44912 KB Output is correct
20 Correct 194 ms 54988 KB Output is correct
21 Correct 22 ms 7872 KB Output is correct
22 Correct 220 ms 74860 KB Output is correct
23 Correct 220 ms 76148 KB Output is correct
24 Correct 232 ms 82036 KB Output is correct
25 Correct 240 ms 86092 KB Output is correct
26 Correct 220 ms 94156 KB Output is correct
27 Correct 458 ms 95572 KB Output is correct
28 Correct 351 ms 99416 KB Output is correct
29 Correct 454 ms 93776 KB Output is correct
30 Correct 190 ms 55840 KB Output is correct
31 Correct 471 ms 98424 KB Output is correct
32 Incorrect 137 ms 15816 KB Output isn't correct
33 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 -