oj.uz

Submission #258702

# Submission time Handle Problem Language Result Execution time Memory
258702 2020-08-06T11:46:31 Z TadijaSebez Sky Walking (IOI19_walk) C++14
100 / 100
 2121 ms 122556 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
const int N=100050;
const int L=17;
const ll inf=9e18;
int rmq[N][L],lgs[N],n,m;
void BuildST(vi h){
	for(int i=0;i<n;i++)rmq[i][0]=h[i];
	for(int j=1;j<L;j++){
		for(int i=0;i<n-(1<<j)+1;i++){
			rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=2;i<=n;i++)lgs[i]=lgs[i>>1]+1;
}
int Get(int l,int r){
	int k=lgs[r-l+1];
	return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
int GetL(int x,int y){
	int top=x,bot=0,mid,ans;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(mid,x)>=y)ans=mid,bot=mid+1;
		else top=mid-1;
	}
	return ans;
}
int GetR(int x,int y){
	int bot=x,top=n-1,mid,ans;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(x,mid)>=y)ans=mid,top=mid-1;
		else bot=mid+1;
	}
	return ans;
}
int tot;
map<int,int> idx[N];
void Add(int x,int y){
	if(!idx[x][y])
		idx[x][y]=++tot;
}
vector<pii> E[N*12];
ll dist[N*12];
void AddEdge(int u,int v,int w){
	E[u].pb({v,w});
	E[v].pb({u,w});
}
ll min_distance(vi x,vi h,vi l,vi r,vi y,int s,int g){
	n=x.size();
	m=l.size();
	BuildST(h);
	Add(s,0);
	Add(g,0);
	vector<pii> evs;
	for(int i=0;i<m;i++){
		Add(l[i],y[i]);
		Add(r[i],y[i]);
		if(l[i]<s&&r[i]>s){
			Add(GetL(s,y[i]),y[i]);
			Add(GetR(s,y[i]),y[i]);
		}
		if(l[i]<g&&r[i]>g){
			Add(GetL(g,y[i]),y[i]);
			Add(GetR(g,y[i]),y[i]);
		}
		evs.pb({l[i],y[i]});
		evs.pb({r[i]+1,-y[i]});
	}
	sort(evs.begin(),evs.end());
	map<int,int> bal;
	for(int i=0,j=0;i<n;i++){
		while(j<evs.size()&&evs[j].first==i){
			int y=evs[j].second;
			bal[abs(y)]+=y/abs(y);
			if(!bal[abs(y)])bal.erase(abs(y));
			j++;
		}
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			auto jt=bal.lower_bound(it->first);
			if(jt!=bal.begin()){
				jt--;
				Add(i,jt->first);
				AddEdge(it->second,idx[i][jt->first],it->first-jt->first);
			}else if(i==s||i==g){
				AddEdge(it->second,idx[i][0],it->first);
			}
		}
	}
	evs.clear();bal.clear();
	for(int i=0;i<m;i++){
		evs.pb({l[i],y[i]});
		evs.pb({r[i],-y[i]});
	}
	sort(evs.begin(),evs.end());
	map<int,pii> las;
	for(int i=0,j=0;i<n;i++){
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			if(las[it->first].first){
				AddEdge(it->second,las[it->first].first,x[i]-las[it->first].second);
			}
		}
		set<int> pos;
		while(j<evs.size()&&evs[j].first==i){
			int y=evs[j].second;
			bal[abs(y)]+=y/abs(y);
			if(!bal[abs(y)])bal.erase(abs(y));
			pos.insert(abs(y));
			j++;
		}
		for(int y:pos){
			if(bal.find(y)==bal.end())las[y]={0,0};
		}
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			if(bal.find(it->first)!=bal.end())
				las[it->first]={it->second,x[i]};
		}
	}
	priority_queue<pair<ll,int>> pq;
	for(int i=1;i<=tot;i++)dist[i]=inf;
	dist[idx[s][0]]=0;
	pq.push({0,idx[s][0]});
	while(pq.size()){
		int u=pq.top().second;
		ll d=-pq.top().first;
		pq.pop();
		if(dist[u]!=d)continue;
		for(auto e:E[u]){
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({-dist[v],v});
			}
		}
	}
	return dist[idx[g][0]]==inf?-1:dist[idx[g][0]];
}

Compilation message

walk.cpp: In function 'void BuildST(std::vector<int>)':
walk.cpp:16:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
                                        ~^~
walk.cpp: In function 'int GetL(int, int)':
walk.cpp:28:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
walk.cpp: In function 'int GetR(int, int)':
walk.cpp:37:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
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:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<evs.size()&&evs[j].first==i){
         ~^~~~~~~~~~~
walk.cpp:110:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<evs.size()&&evs[j].first==i){
         ~^~~~~~~~~~~
walk.cpp: In function 'int GetL(int, int)':
walk.cpp:32:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~
walk.cpp: In function 'int GetR(int, int)':
walk.cpp:41:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33312 KB Output is correct
2 Correct 21 ms 33272 KB Output is correct
3 Correct 20 ms 33280 KB Output is correct
4 Correct 21 ms 33280 KB Output is correct
5 Correct 21 ms 33280 KB Output is correct
6 Correct 24 ms 33272 KB Output is correct
7 Correct 20 ms 33280 KB Output is correct
8 Correct 27 ms 33280 KB Output is correct
9 Correct 20 ms 33280 KB Output is correct
10 Correct 20 ms 33280 KB Output is correct
11 Correct 20 ms 33272 KB Output is correct
12 Correct 21 ms 33280 KB Output is correct
13 Correct 21 ms 33280 KB Output is correct
14 Correct 21 ms 33280 KB Output is correct
15 Correct 21 ms 33280 KB Output is correct
16 Correct 21 ms 33280 KB Output is correct
17 Correct 20 ms 33272 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 33280 KB Output is correct
2 Correct 20 ms 33280 KB Output is correct
3 Correct 859 ms 80804 KB Output is correct
4 Correct 721 ms 90320 KB Output is correct
5 Correct 487 ms 78060 KB Output is correct
6 Correct 526 ms 76372 KB Output is correct
7 Correct 487 ms 78284 KB Output is correct
8 Correct 882 ms 82544 KB Output is correct
9 Correct 666 ms 85940 KB Output is correct
10 Correct 762 ms 91040 KB Output is correct
11 Correct 663 ms 77568 KB Output is correct
12 Correct 425 ms 73188 KB Output is correct
13 Correct 724 ms 92780 KB Output is correct
14 Correct 539 ms 71656 KB Output is correct
15 Correct 487 ms 69992 KB Output is correct
16 Correct 374 ms 67596 KB Output is correct
17 Correct 364 ms 66840 KB Output is correct
18 Correct 679 ms 83948 KB Output is correct
19 Correct 33 ms 35320 KB Output is correct
20 Correct 185 ms 54836 KB Output is correct
21 Correct 303 ms 64840 KB Output is correct
22 Correct 298 ms 66152 KB Output is correct
23 Correct 582 ms 81000 KB Output is correct
24 Correct 327 ms 66948 KB Output is correct
25 Correct 312 ms 66332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 42652 KB Output is correct
2 Correct 1224 ms 86248 KB Output is correct
3 Correct 1219 ms 88296 KB Output is correct
4 Correct 1225 ms 97640 KB Output is correct
5 Correct 1429 ms 100708 KB Output is correct
6 Correct 1389 ms 98156 KB Output is correct
7 Correct 464 ms 71916 KB Output is correct
8 Correct 469 ms 73320 KB Output is correct
9 Correct 1301 ms 97288 KB Output is correct
10 Correct 543 ms 73448 KB Output is correct
11 Correct 38 ms 38528 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 42652 KB Output is correct
2 Correct 1224 ms 86248 KB Output is correct
3 Correct 1219 ms 88296 KB Output is correct
4 Correct 1225 ms 97640 KB Output is correct
5 Correct 1429 ms 100708 KB Output is correct
6 Correct 1389 ms 98156 KB Output is correct
7 Correct 464 ms 71916 KB Output is correct
8 Correct 469 ms 73320 KB Output is correct
9 Correct 1301 ms 97288 KB Output is correct
10 Correct 543 ms 73448 KB Output is correct
11 Correct 38 ms 38528 KB Output is correct
12 Correct 1256 ms 88044 KB Output is correct
13 Correct 1078 ms 97640 KB Output is correct
14 Correct 1455 ms 100712 KB Output is correct
15 Correct 717 ms 84708 KB Output is correct
16 Correct 768 ms 87784 KB Output is correct
17 Correct 816 ms 95268 KB Output is correct
18 Correct 760 ms 84712 KB Output is correct
19 Correct 885 ms 87656 KB Output is correct
20 Correct 553 ms 70636 KB Output is correct
21 Correct 68 ms 44272 KB Output is correct
22 Correct 649 ms 85608 KB Output is correct
23 Correct 597 ms 84584 KB Output is correct
24 Correct 507 ms 76136 KB Output is correct
25 Correct 558 ms 82152 KB Output is correct
26 Correct 465 ms 71776 KB Output is correct
27 Correct 1410 ms 99752 KB Output is correct
28 Correct 883 ms 97128 KB Output is correct
29 Correct 1350 ms 97768 KB Output is correct
30 Correct 494 ms 71916 KB Output is correct
31 Correct 1269 ms 97008 KB Output is correct
32 Correct 401 ms 68888 KB Output is correct
33 Correct 392 ms 69864 KB Output is correct
34 Correct 518 ms 75752 KB Output is correct
35 Correct 484 ms 73720 KB Output is correct
36 Correct 368 ms 69896 KB Output is correct
37 Correct 296 ms 64844 KB Output is correct
38 Correct 290 ms 66152 KB Output is correct
39 Correct 573 ms 81000 KB Output is correct
40 Correct 326 ms 67076 KB Output is correct
41 Correct 321 ms 66332 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33312 KB Output is correct
2 Correct 21 ms 33272 KB Output is correct
3 Correct 20 ms 33280 KB Output is correct
4 Correct 21 ms 33280 KB Output is correct
5 Correct 21 ms 33280 KB Output is correct
6 Correct 24 ms 33272 KB Output is correct
7 Correct 20 ms 33280 KB Output is correct
8 Correct 27 ms 33280 KB Output is correct
9 Correct 20 ms 33280 KB Output is correct
10 Correct 20 ms 33280 KB Output is correct
11 Correct 20 ms 33272 KB Output is correct
12 Correct 21 ms 33280 KB Output is correct
13 Correct 21 ms 33280 KB Output is correct
14 Correct 21 ms 33280 KB Output is correct
15 Correct 21 ms 33280 KB Output is correct
16 Correct 21 ms 33280 KB Output is correct
17 Correct 20 ms 33272 KB Output is correct
18 Correct 21 ms 33280 KB Output is correct
19 Correct 20 ms 33280 KB Output is correct
20 Correct 859 ms 80804 KB Output is correct
21 Correct 721 ms 90320 KB Output is correct
22 Correct 487 ms 78060 KB Output is correct
23 Correct 526 ms 76372 KB Output is correct
24 Correct 487 ms 78284 KB Output is correct
25 Correct 882 ms 82544 KB Output is correct
26 Correct 666 ms 85940 KB Output is correct
27 Correct 762 ms 91040 KB Output is correct
28 Correct 663 ms 77568 KB Output is correct
29 Correct 425 ms 73188 KB Output is correct
30 Correct 724 ms 92780 KB Output is correct
31 Correct 539 ms 71656 KB Output is correct
32 Correct 487 ms 69992 KB Output is correct
33 Correct 374 ms 67596 KB Output is correct
34 Correct 364 ms 66840 KB Output is correct
35 Correct 679 ms 83948 KB Output is correct
36 Correct 33 ms 35320 KB Output is correct
37 Correct 185 ms 54836 KB Output is correct
38 Correct 303 ms 64840 KB Output is correct
39 Correct 298 ms 66152 KB Output is correct
40 Correct 582 ms 81000 KB Output is correct
41 Correct 327 ms 66948 KB Output is correct
42 Correct 312 ms 66332 KB Output is correct
43 Correct 115 ms 42652 KB Output is correct
44 Correct 1224 ms 86248 KB Output is correct
45 Correct 1219 ms 88296 KB Output is correct
46 Correct 1225 ms 97640 KB Output is correct
47 Correct 1429 ms 100708 KB Output is correct
48 Correct 1389 ms 98156 KB Output is correct
49 Correct 464 ms 71916 KB Output is correct
50 Correct 469 ms 73320 KB Output is correct
51 Correct 1301 ms 97288 KB Output is correct
52 Correct 543 ms 73448 KB Output is correct
53 Correct 38 ms 38528 KB Output is correct
54 Correct 1256 ms 88044 KB Output is correct
55 Correct 1078 ms 97640 KB Output is correct
56 Correct 1455 ms 100712 KB Output is correct
57 Correct 717 ms 84708 KB Output is correct
58 Correct 768 ms 87784 KB Output is correct
59 Correct 816 ms 95268 KB Output is correct
60 Correct 760 ms 84712 KB Output is correct
61 Correct 885 ms 87656 KB Output is correct
62 Correct 553 ms 70636 KB Output is correct
63 Correct 68 ms 44272 KB Output is correct
64 Correct 649 ms 85608 KB Output is correct
65 Correct 597 ms 84584 KB Output is correct
66 Correct 507 ms 76136 KB Output is correct
67 Correct 558 ms 82152 KB Output is correct
68 Correct 465 ms 71776 KB Output is correct
69 Correct 1410 ms 99752 KB Output is correct
70 Correct 883 ms 97128 KB Output is correct
71 Correct 1350 ms 97768 KB Output is correct
72 Correct 494 ms 71916 KB Output is correct
73 Correct 1269 ms 97008 KB Output is correct
74 Correct 401 ms 68888 KB Output is correct
75 Correct 392 ms 69864 KB Output is correct
76 Correct 518 ms 75752 KB Output is correct
77 Correct 484 ms 73720 KB Output is correct
78 Correct 368 ms 69896 KB Output is correct
79 Correct 296 ms 64844 KB Output is correct
80 Correct 290 ms 66152 KB Output is correct
81 Correct 573 ms 81000 KB Output is correct
82 Correct 326 ms 67076 KB Output is correct
83 Correct 321 ms 66332 KB Output is correct
84 Correct 94 ms 40812 KB Output is correct
85 Correct 1254 ms 89200 KB Output is correct
86 Correct 1732 ms 110192 KB Output is correct
87 Correct 89 ms 47344 KB Output is correct
88 Correct 97 ms 47856 KB Output is correct
89 Correct 88 ms 47344 KB Output is correct
90 Correct 41 ms 36424 KB Output is correct
91 Correct 21 ms 33408 KB Output is correct
92 Correct 44 ms 36096 KB Output is correct
93 Correct 360 ms 62188 KB Output is correct
94 Correct 72 ms 44528 KB Output is correct
95 Correct 700 ms 87912 KB Output is correct
96 Correct 614 ms 84712 KB Output is correct
97 Correct 545 ms 76008 KB Output is correct
98 Correct 560 ms 81896 KB Output is correct
99 Correct 2121 ms 122556 KB Output is correct
100 Correct 1051 ms 97736 KB Output is correct
101 Correct 1617 ms 105064 KB Output is correct
102 Correct 474 ms 71912 KB Output is correct
103 Correct 405 ms 68768 KB Output is correct
104 Correct 396 ms 69604 KB Output is correct
105 Correct 507 ms 75496 KB Output is correct
106 Correct 463 ms 72168 KB Output is correct
107 Correct 519 ms 75888 KB Output is correct
108 Correct 76 ms 38392 KB Output is correct
109 Correct 976 ms 85952 KB Output is correct
110 Correct 904 ms 96104 KB Output is correct
111 Correct 897 ms 96232 KB Output is correct
112 Correct 486 ms 73140 KB Output is correct
113 Correct 448 ms 71300 KB Output is correct