oj.uz

Submission #379366

# Submission time Handle Problem Language Result Execution time Memory
379366 2021-03-18T03:20:53 Z Thistle Sky Walking (IOI19_walk) C++14
24 / 100
 1590 ms 755416 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(4000000);
	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 62 ms 94188 KB Output is correct
2 Correct 62 ms 94188 KB Output is correct
3 Correct 68 ms 94316 KB Output is correct
4 Correct 64 ms 94188 KB Output is correct
5 Correct 63 ms 94344 KB Output is correct
6 Correct 64 ms 94316 KB Output is correct
7 Correct 63 ms 94444 KB Output is correct
8 Correct 63 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 63 ms 94444 KB Output is correct
11 Correct 63 ms 94316 KB Output is correct
12 Correct 63 ms 94336 KB Output is correct
13 Correct 62 ms 94316 KB Output is correct
14 Correct 65 ms 94316 KB Output is correct
15 Correct 65 ms 94188 KB Output is correct
16 Correct 65 ms 94316 KB Output is correct
17 Correct 73 ms 94316 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94188 KB Output is correct
2 Correct 65 ms 94224 KB Output is correct
3 Correct 895 ms 179564 KB Output is correct
4 Correct 1187 ms 203368 KB Output is correct
5 Correct 841 ms 191316 KB Output is correct
6 Correct 809 ms 185044 KB Output is correct
7 Correct 827 ms 194644 KB Output is correct
8 Correct 1135 ms 203276 KB Output is correct
9 Correct 942 ms 189500 KB Output is correct
10 Correct 1590 ms 240468 KB Output is correct
11 Correct 671 ms 149520 KB Output is correct
12 Correct 574 ms 145620 KB Output is correct
13 Correct 1419 ms 226684 KB Output is correct
14 Correct 474 ms 143888 KB Output is correct
15 Correct 563 ms 144980 KB Output is correct
16 Correct 588 ms 143436 KB Output is correct
17 Correct 556 ms 142180 KB Output is correct
18 Correct 383 ms 145988 KB Output is correct
19 Correct 70 ms 96620 KB Output is correct
20 Correct 139 ms 118840 KB Output is correct
21 Correct 523 ms 137976 KB Output is correct
22 Correct 573 ms 144792 KB Output is correct
23 Correct 619 ms 154128 KB Output is correct
24 Correct 582 ms 143532 KB Output is correct
25 Correct 521 ms 141808 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 110060 KB Output is correct
2 Runtime error 1582 ms 755416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 110060 KB Output is correct
2 Runtime error 1582 ms 755416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94188 KB Output is correct
2 Correct 62 ms 94188 KB Output is correct
3 Correct 68 ms 94316 KB Output is correct
4 Correct 64 ms 94188 KB Output is correct
5 Correct 63 ms 94344 KB Output is correct
6 Correct 64 ms 94316 KB Output is correct
7 Correct 63 ms 94444 KB Output is correct
8 Correct 63 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 63 ms 94444 KB Output is correct
11 Correct 63 ms 94316 KB Output is correct
12 Correct 63 ms 94336 KB Output is correct
13 Correct 62 ms 94316 KB Output is correct
14 Correct 65 ms 94316 KB Output is correct
15 Correct 65 ms 94188 KB Output is correct
16 Correct 65 ms 94316 KB Output is correct
17 Correct 73 ms 94316 KB Output is correct
18 Correct 64 ms 94188 KB Output is correct
19 Correct 65 ms 94224 KB Output is correct
20 Correct 895 ms 179564 KB Output is correct
21 Correct 1187 ms 203368 KB Output is correct
22 Correct 841 ms 191316 KB Output is correct
23 Correct 809 ms 185044 KB Output is correct
24 Correct 827 ms 194644 KB Output is correct
25 Correct 1135 ms 203276 KB Output is correct
26 Correct 942 ms 189500 KB Output is correct
27 Correct 1590 ms 240468 KB Output is correct
28 Correct 671 ms 149520 KB Output is correct
29 Correct 574 ms 145620 KB Output is correct
30 Correct 1419 ms 226684 KB Output is correct
31 Correct 474 ms 143888 KB Output is correct
32 Correct 563 ms 144980 KB Output is correct
33 Correct 588 ms 143436 KB Output is correct
34 Correct 556 ms 142180 KB Output is correct
35 Correct 383 ms 145988 KB Output is correct
36 Correct 70 ms 96620 KB Output is correct
37 Correct 139 ms 118840 KB Output is correct
38 Correct 523 ms 137976 KB Output is correct
39 Correct 573 ms 144792 KB Output is correct
40 Correct 619 ms 154128 KB Output is correct
41 Correct 582 ms 143532 KB Output is correct
42 Correct 521 ms 141808 KB Output is correct
43 Correct 172 ms 110060 KB Output is correct
44 Runtime error 1582 ms 755416 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -