oj.uz

Submission #823401

# Submission time Handle Problem Language Result Execution time Memory
823401 2023-08-12T13:17:26 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
0 / 100
 504 ms 130560 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);
	}
};

const int N=1e5+55;
vector<pi> adj[10*N];
ll d[10*N];

map<int,int> c[N]; int _z=0; const int Z=1e9+5;
int ind(int x, int y) {
	if (c[x].count(y)) return c[x][y];
	return c[x][y]=_z++;
}
#undef int

ll p12(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();
	
	vector<vector<int>> g1(n);
	vector<vector<int>> g2(m);
	g1[s].pb(0);
	g1[g].pb(0);

	vector<pi> v;
	forn(i,n) v.pb({h[i],i});
	forn(i,m) v.pb({y[i],-i-1});
	sort(rall(v));

	set<int> st;
	for(auto&z:v) {
		int y=z.f, i=z.s;
		if (i>=0) {
			st.insert(i); continue;
		}
		i*=-1; --i;
		auto it=st.upper_bound(l[i]);
		vector<int> v;
		while (1) {
			int j=*it;
			v.pb(j);
			if (j==r[i]) break;
			++it;
		}
		if (v.size() > 10 && max(n,m)>50) return -2;
		g1[l[i]].pb(y);
		int last=l[i];
		for(auto&j:v) {
			adj[ind(last,y)].pb({ind(j,y),x[j]-x[last]});
			adj[ind(j,y)].pb({ind(last,y),x[j]-x[last]});
			g1[j].pb(y);
			last=j;
		}
	}

	forn(i,n) {
		sort(all(g1[i]));
		int sz=g1[i].size();
		forn(j,sz-1) {
			adj[ind(i,g1[i][j])].pb({ind(i,g1[i][j+1]),g1[i][j+1]-g1[i][j]});
			adj[ind(i,g1[i][j+1])].pb({ind(i,g1[i][j]),g1[i][j+1]-g1[i][j]});
		}
	}

	forn(i,_z) d[i]=inf;
	priority_queue<pair<ll,ll>> q; q.push({0,ind(s,0)});

	while(q.size()) {
		auto it=q.top(); q.pop();
		ll di=-it.f, u=it.s;
		if (d[u]<=di) continue;
		d[u]=di;
		for(auto&e:adj[u]) {
			int v=e.f, w=e.s;
			if (d[v]!=inf) continue;
			q.push({-di-w,v});
		}
	}

	if (d[ind(g,0)]==inf) return -1;
	return d[ind(g,0)];
}

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();

	//auto z = p12(x,h,l,r,y,s,g);
	//if (z!=-2) return z;
	
	#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]+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) exit(1);//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 15 ms 28500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 31912 KB Output is correct
2 Correct 415 ms 122696 KB Output is correct
3 Correct 415 ms 108908 KB Output is correct
4 Correct 454 ms 127572 KB Output is correct
5 Correct 504 ms 128420 KB Output is correct
6 Correct 489 ms 130560 KB Output is correct
7 Correct 210 ms 84000 KB Output is correct
8 Correct 345 ms 122192 KB Output is correct
9 Correct 466 ms 126564 KB Output is correct
10 Correct 149 ms 47668 KB Output is correct
11 Runtime error 24 ms 31600 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 31912 KB Output is correct
2 Correct 415 ms 122696 KB Output is correct
3 Correct 415 ms 108908 KB Output is correct
4 Correct 454 ms 127572 KB Output is correct
5 Correct 504 ms 128420 KB Output is correct
6 Correct 489 ms 130560 KB Output is correct
7 Correct 210 ms 84000 KB Output is correct
8 Correct 345 ms 122192 KB Output is correct
9 Correct 466 ms 126564 KB Output is correct
10 Correct 149 ms 47668 KB Output is correct
11 Runtime error 24 ms 31600 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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