oj.uz

Submission #379365

# Submission time Handle Problem Language Result Execution time Memory
379365 2021-03-18T03:20:21 Z Thistle Sky Walking (IOI19_walk) C++14
10 / 100
 88 ms 25580 KB 
#include "walk.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
#define pb emplace_back

class sptable{
	int n;
	vi lgt;
	vec<vi> dat;
public:
	sptable(vec<int> v){
		n=siz(v);
		lgt.assign(n+1,0);
		for(int i=2;i<=n;i++) lgt[i]=lgt[i>>1]+1;
		
		dat.assign(lgt[n]+1,vi(n));
		
		rep(i,n) dat[0][i]=v[i];
		rng(i,0,lgt[n]){
			for(int j=0;j+(1<<(i+1))<=n;j++){
				dat[i+1][j]=max(dat[i][j],dat[i][j+(1<<i)]);
			}
		}
	}
	sptable(){}
	ll get(int l,int r){
		if(r<=l) return -1;
		int k=lgt[r-l];
		return max(dat[k][l],dat[k][r-(1<<k)]);
	}
};

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n=siz(x);
	int m=siz(l);
	//x=place
	//h=height
	//l,r,y=road
	//s,g=start,goal

	int num=n;
	vec<vec<H>>pos(n);
	rep(i,n) pos[i].pb(H{0,i});
	vec<vec<H>>e(100000);
	sptable spt(h);
	
	
	rep(i,m){
		int st=l[i];
		while(st!=r[i]){
			pos[st].pb(H{y[i],num++});
			int ok=n,ng=st+1,mid;
			while(ok-ng>1){
				mid=(ok+ng)/2;
				if(spt.get(st+1,mid)>=y[i]) ok=mid;
				else ng=mid;
			}
			ok--;
			e[num-1].pb(H{num,x[ok]-x[st]});
			e[num].pb(H{num-1,x[ok]-x[st]});
			st=ok;
		}
		pos[st].pb(H{y[i],num++});
	}

	
	rep(i,n){
		sort(all(pos[i]));
		rep(j,siz(pos[i])-1){
			e[pos[i][j].sc].pb(H{pos[i][j+1].sc,pos[i][j+1].fs-pos[i][j].fs});
			e[pos[i][j+1].sc].pb(H{pos[i][j].sc,pos[i][j+1].fs-pos[i][j].fs});
		}
	}
	
	priority_queue<H, vec<H>, greater<H>>p;
	vec<ll>a(num,1e17);
	a[s]=0;
	p.push(H{0,s});
	while(!p.empty()){
		H t=p.top();p.pop();
		if(t.fs!=a[t.sc]) continue;
		for(auto g:e[t.sc]){
			if(a[g.fs]>t.fs+g.sc){
				a[g.fs]=t.fs+g.sc;
				p.push(H{a[g.fs],g.fs});
			}
		}
	}
	if(a[g]==1e17) a[g]=-1;
	return a[g];
}

Compilation message

walk.cpp: In constructor 'sptable::sptable(std::vector<int>)':
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:30:3: note: in expansion of macro 'rep'
   30 |   rep(i,n) dat[0][i]=v[i];
      |   ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:31:3: note: in expansion of macro 'rng'
   31 |   rng(i,0,lgt[n]){
      |   ^~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:55:2: note: in expansion of macro 'rep'
   55 |  rep(i,n) pos[i].pb(H{0,i});
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:60:2: note: in expansion of macro 'rep'
   60 |  rep(i,m){
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:79:2: note: in expansion of macro 'rep'
   79 |  rep(i,n){
      |  ^~~
walk.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
walk.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
walk.cpp:81:3: note: in expansion of macro 'rep'
   81 |   rep(j,siz(pos[i])-1){
      |   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 3 ms 2796 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Runtime error 88 ms 25580 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 21996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 21996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2944 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2668 KB Output is correct
17 Correct 3 ms 2796 KB Output is correct
18 Correct 2 ms 2668 KB Output is correct
19 Correct 2 ms 2668 KB Output is correct
20 Runtime error 88 ms 25580 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -