| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 411411 |
2021-05-25T08:41:17 Z |
조영욱(#7626) |
Sky Walking (IOI19_walk) |
C++17 |
|
2282 ms |
279068 KB |
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<long long,long long> P;
vector<int> v[100000];
const int sz=131072;
int ssum[100000];
vector<P> adj[1500000];
long long dist[1500000];
bool vis[1500000];
P pmax(P a,P b) {
return a<b?b:a;
}
P seg[sz*2];
P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
if (r<nodel||l>noder) {
return P(-1,-1);
}
if (l<=nodel&&noder<=r) {
return seg[node];
}
int mid=(nodel+noder)/2;
return pmax(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}
void update(int i,P val) {
i+=sz;
seg[i]=val;
while (i>1) {
i/=2;
seg[i]=pmax(seg[i*2],seg[i*2+1]);
}
}
long long min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s, int g) {
n=x.size();
m=y.size();
//printf("%d %d\n",n,m);
for(int i=0;i<n;i++) {
update(i,P(h[i],i));
}
for(int i=0;i<m;i++) {
vector<P> vec;
while (1) {
P got=sum(l[i],r[i]);
if (got.first<y[i]) {
for(int ind=0;ind<vec.size();ind++) {
update(vec[ind].second,vec[ind]);
}
break;
}
vec.push_back(got);
v[got.second].push_back(y[i]);
update(got.second,P(-1,-1));
}
}
for(int i=0;i<n;i++) {
v[i].push_back(0);
sort(v[i].begin(),v[i].end());
if (i) {
ssum[i]=ssum[i-1]+v[i-1].size();
}
for(int j=1;j<v[i].size();j++) {
long long dist=v[i][j]-v[i][j-1];
adj[ssum[i]+j-1].push_back(P(ssum[i]+j,dist));
adj[ssum[i]+j].push_back(P(ssum[i]+j-1,dist));
//printf("%d %d %lld\n",ssum[i]+j-1,ssum[i]+j,dist);
}
}
for(int i=0;i<m;i++) {
vector<P> vec;
vector<P> vec2;
while (1) {
P got=sum(l[i],r[i]);
if (got.first<y[i]) {
for(int ind=0;ind<vec.size();ind++) {
update(vec[ind].second,vec[ind]);
}
break;
}
vec.push_back(got);
update(got.second,P(-1,-1));
vec2.push_back(P(got.second,y[i]));
}
sort(vec2.begin(),vec2.end());
for(int j=0;j+1<vec2.size();j++) {
int ind1=ssum[vec2[j].first]+lower_bound(v[vec2[j].first].begin(),v[vec2[j].first].end(),y[i])-v[vec2[j].first].begin();
int ind2=ssum[vec2[j+1].first]+lower_bound(v[vec2[j+1].first].begin(),v[vec2[j+1].first].end(),y[i])-v[vec2[j+1].first].begin();
long long dist=x[vec2[j+1].first]-x[vec2[j].first];
adj[ind1].push_back(P(ind2,dist));
adj[ind2].push_back(P(ind1,dist));
//printf("%d %d %lld\n",ind1,ind2,dist);
}
}
int gsz=ssum[n-1]+v[n-1].size();
for(int i=0;i<sz;i++) {
dist[i]=1e16;
}
priority_queue<P,vector<P>,greater<P>> pq;
pq.push(P(0,ssum[s]));
dist[ssum[s]]=0;
while (!pq.empty()) {
int now;
do {
now=pq.top().second;
pq.pop();
} while (!pq.empty()&&vis[now]);
if (vis[now]) {
break;
}
vis[now]=true;
for(int i=0;i<adj[now].size();i++) {
int nt=adj[now][i].first;
if (dist[nt]>dist[now]+adj[now][i].second) {
dist[nt]=dist[now]+adj[now][i].second;
pq.push(P(dist[nt],nt));
}
}
}
long long INF=5e15;
return dist[ssum[g]]>INF?-1:dist[ssum[g]];
}
Compilation message
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:52:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int ind=0;ind<vec.size();ind++) {
| ~~~^~~~~~~~~~~
walk.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int j=1;j<v[i].size();j++) {
| ~^~~~~~~~~~~~
walk.cpp:81:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int ind=0;ind<vec.size();ind++) {
| ~~~^~~~~~~~~~~
walk.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int j=0;j+1<vec2.size();j++) {
| ~~~^~~~~~~~~~~~
walk.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
walk.cpp:100:9: warning: unused variable 'gsz' [-Wunused-variable]
100 | int gsz=ssum[n-1]+v[n-1].size();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
38860 KB |
Output is correct |
| 2 |
Correct |
23 ms |
38884 KB |
Output is correct |
| 3 |
Correct |
22 ms |
38984 KB |
Output is correct |
| 4 |
Correct |
24 ms |
38936 KB |
Output is correct |
| 5 |
Correct |
24 ms |
38980 KB |
Output is correct |
| 6 |
Correct |
24 ms |
38988 KB |
Output is correct |
| 7 |
Correct |
24 ms |
38896 KB |
Output is correct |
| 8 |
Correct |
24 ms |
38968 KB |
Output is correct |
| 9 |
Correct |
23 ms |
38976 KB |
Output is correct |
| 10 |
Correct |
28 ms |
39040 KB |
Output is correct |
| 11 |
Correct |
24 ms |
38872 KB |
Output is correct |
| 12 |
Correct |
24 ms |
38988 KB |
Output is correct |
| 13 |
Correct |
26 ms |
38860 KB |
Output is correct |
| 14 |
Correct |
24 ms |
38860 KB |
Output is correct |
| 15 |
Correct |
24 ms |
38964 KB |
Output is correct |
| 16 |
Correct |
24 ms |
38928 KB |
Output is correct |
| 17 |
Correct |
24 ms |
38980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
38876 KB |
Output is correct |
| 2 |
Correct |
24 ms |
38960 KB |
Output is correct |
| 3 |
Incorrect |
1394 ms |
109388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
50824 KB |
Output is correct |
| 2 |
Runtime error |
2282 ms |
279068 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
50824 KB |
Output is correct |
| 2 |
Runtime error |
2282 ms |
279068 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
38860 KB |
Output is correct |
| 2 |
Correct |
23 ms |
38884 KB |
Output is correct |
| 3 |
Correct |
22 ms |
38984 KB |
Output is correct |
| 4 |
Correct |
24 ms |
38936 KB |
Output is correct |
| 5 |
Correct |
24 ms |
38980 KB |
Output is correct |
| 6 |
Correct |
24 ms |
38988 KB |
Output is correct |
| 7 |
Correct |
24 ms |
38896 KB |
Output is correct |
| 8 |
Correct |
24 ms |
38968 KB |
Output is correct |
| 9 |
Correct |
23 ms |
38976 KB |
Output is correct |
| 10 |
Correct |
28 ms |
39040 KB |
Output is correct |
| 11 |
Correct |
24 ms |
38872 KB |
Output is correct |
| 12 |
Correct |
24 ms |
38988 KB |
Output is correct |
| 13 |
Correct |
26 ms |
38860 KB |
Output is correct |
| 14 |
Correct |
24 ms |
38860 KB |
Output is correct |
| 15 |
Correct |
24 ms |
38964 KB |
Output is correct |
| 16 |
Correct |
24 ms |
38928 KB |
Output is correct |
| 17 |
Correct |
24 ms |
38980 KB |
Output is correct |
| 18 |
Correct |
24 ms |
38876 KB |
Output is correct |
| 19 |
Correct |
24 ms |
38960 KB |
Output is correct |
| 20 |
Incorrect |
1394 ms |
109388 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
