oj.uz

Submission #426439

# Submission time Handle Problem Language Result Execution time Memory
426439 2021-06-14T03:24:22 Z mhy908 Sky Walking (IOI19_walk) C++14
100 / 100
 3204 ms 269068 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

int n, m, toy[200010], s, e;
vector<int> idy;

vector<pii> poss;
int x[100010], h[100010], l[100010], r[100010], y[100010];

vector<int> deln[200010];
vector<pii> line[200010];
vector<int> updm[100010], delm[100010];

vector<int> possx[100010], possy[200010];

map<pii, int> num;
int re;

vector<pil> link[2000010];
LL dist[2000010];
priority_queue<pli, vector<pli>, greater<pli> > pq;

void dbg(){
    for(auto i:idy)printf("%d ", i);
    puts("");
    for(auto i:num)printf("%d -> %d %d\n", i.S, i.F.F-1, toy[i.F.S]);
    while(1){
        int t;
        scanf("%d", &t);
        if(t==0)return;
        for(auto i:link[t])printf("LINK = %d %lld\n", i.F, i.S);
    }
}

LL min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int E){
	n=X.size(); m=Y.size();
	s=min(S, E)+1; e=max(S, E)+1;

	for(auto i:H)idy.eb(i);
	for(auto i:Y)idy.eb(i);
	svec(idy); press(idy);

	for(auto &i:H){
        int tmp=lower_bound(all(idy), i)-idy.begin()+1;
        toy[tmp]=i;
        i=tmp;
	}
	for(auto &i:Y){
        int tmp=lower_bound(all(idy), i)-idy.begin()+1;
        toy[tmp]=i;
        i=tmp;
	}

	for(int i=0; i<n; i++)x[i+1]=X[i];
	for(int i=0; i<n; i++)h[i+1]=H[i];
	for(int i=0; i<m; i++)l[i+1]=L[i]+1;
	for(int i=0; i<m; i++)r[i+1]=R[i]+1;
	for(int i=0; i<m; i++)y[i+1]=Y[i];

	for(int i=1; i<=n; i++)deln[h[i]].eb(i);
	for(int i=1; i<=m; i++){
        line[y[i]].eb(l[i], r[i]);
        updm[l[i]].eb(y[i]);
        delm[r[i]].eb(y[i]);
	}

	set<int> sx;
	for(int i=1; i<=n; i++)sx.insert(i);

	for(int i=1; i<=n+m; i++){
        for(auto j:line[i]){
            poss.eb(j.F, i);
            poss.eb(j.S, i);
            auto it=sx.upper_bound(s);
            if(it!=sx.end()){
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            if(it!=sx.begin()){
                it--;
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            it=sx.upper_bound(e);
            if(it!=sx.end()){
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
            if(it!=sx.begin()){
                it--;
                if(j.F<=*it&&*it<=j.S)poss.eb(*it, i);
            }
        }
        for(auto j:deln[i])sx.erase(j);
	}
	svec(poss); press(poss);
    for(auto i:poss)possx[i.F].eb(i.S);

	set<int> sy;
	sy.insert(0);

	for(int i=1; i<=n; i++){
        vector<int> vcvc;
        for(auto j:updm[i]){
            if(sy.find(j)!=sy.end())vcvc.eb(j);
            sy.insert(j);
        }
        for(auto j:possx[i]){
            auto it=sy.lower_bound(j);
            if(it!=sy.begin()){
                it--;
                poss.eb(i, *it);
                it++;
            }
            it++;
            if(it!=sy.end()){
                if(*it<=h[i])poss.eb(i, *it);
            }
            it--;
        }
        for(auto j:delm[i])sy.erase(j);
        for(auto j:vcvc)sy.insert(j);
	}
	for(int i=1; i<=n; i++)poss.eb(i, 0);
	svec(poss); press(poss);

	for(int i=1; i<=n; i++)possx[i].clear();

	for(auto i:poss){
        num[i]=++re;
        possx[i.F].eb(i.S);
        possy[i.S].eb(i.F);
	}

	for(int i=1; i<=n; i++){
        svec(possx[i]);
        for(int j=1; j<possx[i].size(); j++){
            LL d=(LL)toy[possx[i][j]]-(LL)toy[possx[i][j-1]];
            int st=num[mp(i, possx[i][j-1])];
            int fin=num[mp(i, possx[i][j])];
            link[st].eb(fin, d);
            link[fin].eb(st, d);
        }
	}

	for(int i=1; i<=n+m; i++){
        if(possy[i].size()<=1)continue;
        vector<pii> updvc;
        for(auto j:line[i]){
            updvc.eb(j.F, 1);
            updvc.eb(j.S, -1);
        }
        svec(possy[i]);
        svec(updvc);
        int pv=0, sum=0;
        for(int j=0; j<possy[i].size()-1; j++){
            for(; pv<updvc.size(); pv++){
                if(possy[i][j]<updvc[pv].F)break;
                sum+=updvc[pv].S;
            }
            if(!sum)continue;
            LL d=(LL)x[possy[i][j+1]]-(LL)x[possy[i][j]];
            int st=num[mp(possy[i][j], i)];
            int fin=num[mp(possy[i][j+1], i)];
            link[st].eb(fin, d);
            link[fin].eb(st, d);
        }
	}

    //dbg();

	for(int i=1; i<=re; i++)dist[i]=LLINF;
	pq.push(mp(0ll, num[mp(s, 0)]));

	while(pq.size()){
        int nw=pq.top().S; LL d=pq.top().F;
        pq.pop();
        if(dist[nw]<=d)continue;
        dist[nw]=d;
        for(auto i:link[nw])pq.push(mp(d+i.S, i.F));
	}

	/*
    for(auto i:num){
        printf("%d %d -> %lld\n", i.F.F-1, toy[i.F.S], dist[i.S]);
    }
    */
    if(dist[num[mp(e, 0)]]==LLINF)return -1;
	return dist[num[mp(e, 0)]];
}

Compilation message

walk.cpp: In function 'LL min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for(int j=1; j<possx[i].size(); j++){
      |                      ~^~~~~~~~~~~~~~~~
walk.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for(int j=0; j<possy[i].size()-1; j++){
      |                      ~^~~~~~~~~~~~~~~~~~
walk.cpp:169:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |             for(; pv<updvc.size(); pv++){
      |                   ~~^~~~~~~~~~~~~
walk.cpp: In function 'void dbg()':
walk.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68420 KB Output is correct
2 Correct 39 ms 68340 KB Output is correct
3 Correct 42 ms 68344 KB Output is correct
4 Correct 38 ms 68420 KB Output is correct
5 Correct 39 ms 68500 KB Output is correct
6 Correct 43 ms 68428 KB Output is correct
7 Correct 43 ms 68428 KB Output is correct
8 Correct 39 ms 68420 KB Output is correct
9 Correct 40 ms 68552 KB Output is correct
10 Correct 41 ms 68440 KB Output is correct
11 Correct 42 ms 68420 KB Output is correct
12 Correct 40 ms 68408 KB Output is correct
13 Correct 42 ms 68344 KB Output is correct
14 Correct 42 ms 68424 KB Output is correct
15 Correct 41 ms 68320 KB Output is correct
16 Correct 41 ms 68452 KB Output is correct
17 Correct 39 ms 68436 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 68404 KB Output is correct
2 Correct 38 ms 68420 KB Output is correct
3 Correct 1361 ms 157672 KB Output is correct
4 Correct 1526 ms 183060 KB Output is correct
5 Correct 956 ms 160164 KB Output is correct
6 Correct 922 ms 153564 KB Output is correct
7 Correct 976 ms 160296 KB Output is correct
8 Correct 1520 ms 164632 KB Output is correct
9 Correct 1304 ms 171536 KB Output is correct
10 Correct 1705 ms 186016 KB Output is correct
11 Correct 1206 ms 147904 KB Output is correct
12 Correct 890 ms 143052 KB Output is correct
13 Correct 1740 ms 192880 KB Output is correct
14 Correct 707 ms 136816 KB Output is correct
15 Correct 652 ms 135440 KB Output is correct
16 Correct 635 ms 134180 KB Output is correct
17 Correct 615 ms 130996 KB Output is correct
18 Correct 658 ms 135956 KB Output is correct
19 Correct 65 ms 71748 KB Output is correct
20 Correct 315 ms 102756 KB Output is correct
21 Correct 561 ms 128868 KB Output is correct
22 Correct 581 ms 136588 KB Output is correct
23 Correct 774 ms 150196 KB Output is correct
24 Correct 600 ms 133864 KB Output is correct
25 Correct 623 ms 130052 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 85588 KB Output is correct
2 Correct 1488 ms 178840 KB Output is correct
3 Correct 1906 ms 185124 KB Output is correct
4 Correct 2286 ms 210264 KB Output is correct
5 Correct 2440 ms 211912 KB Output is correct
6 Correct 2246 ms 204920 KB Output is correct
7 Correct 1172 ms 151580 KB Output is correct
8 Correct 875 ms 139652 KB Output is correct
9 Correct 1941 ms 197520 KB Output is correct
10 Correct 712 ms 147736 KB Output is correct
11 Correct 89 ms 76608 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 85588 KB Output is correct
2 Correct 1488 ms 178840 KB Output is correct
3 Correct 1906 ms 185124 KB Output is correct
4 Correct 2286 ms 210264 KB Output is correct
5 Correct 2440 ms 211912 KB Output is correct
6 Correct 2246 ms 204920 KB Output is correct
7 Correct 1172 ms 151580 KB Output is correct
8 Correct 875 ms 139652 KB Output is correct
9 Correct 1941 ms 197520 KB Output is correct
10 Correct 712 ms 147736 KB Output is correct
11 Correct 89 ms 76608 KB Output is correct
12 Correct 1879 ms 185260 KB Output is correct
13 Correct 1797 ms 210220 KB Output is correct
14 Correct 2497 ms 214372 KB Output is correct
15 Correct 1556 ms 184484 KB Output is correct
16 Correct 1613 ms 190076 KB Output is correct
17 Correct 1888 ms 211428 KB Output is correct
18 Correct 1554 ms 184480 KB Output is correct
19 Correct 1603 ms 190108 KB Output is correct
20 Correct 1235 ms 151224 KB Output is correct
21 Correct 228 ms 89112 KB Output is correct
22 Correct 1239 ms 179720 KB Output is correct
23 Correct 1169 ms 173812 KB Output is correct
24 Correct 847 ms 147068 KB Output is correct
25 Correct 1105 ms 168872 KB Output is correct
26 Correct 691 ms 136700 KB Output is correct
27 Correct 2397 ms 214924 KB Output is correct
28 Correct 1751 ms 210188 KB Output is correct
29 Correct 2195 ms 205380 KB Output is correct
30 Correct 1171 ms 153568 KB Output is correct
31 Correct 2045 ms 200160 KB Output is correct
32 Correct 651 ms 140064 KB Output is correct
33 Correct 648 ms 141104 KB Output is correct
34 Correct 722 ms 146976 KB Output is correct
35 Correct 880 ms 151384 KB Output is correct
36 Correct 751 ms 139392 KB Output is correct
37 Correct 546 ms 128896 KB Output is correct
38 Correct 582 ms 136508 KB Output is correct
39 Correct 775 ms 150192 KB Output is correct
40 Correct 595 ms 133800 KB Output is correct
41 Correct 626 ms 130004 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68420 KB Output is correct
2 Correct 39 ms 68340 KB Output is correct
3 Correct 42 ms 68344 KB Output is correct
4 Correct 38 ms 68420 KB Output is correct
5 Correct 39 ms 68500 KB Output is correct
6 Correct 43 ms 68428 KB Output is correct
7 Correct 43 ms 68428 KB Output is correct
8 Correct 39 ms 68420 KB Output is correct
9 Correct 40 ms 68552 KB Output is correct
10 Correct 41 ms 68440 KB Output is correct
11 Correct 42 ms 68420 KB Output is correct
12 Correct 40 ms 68408 KB Output is correct
13 Correct 42 ms 68344 KB Output is correct
14 Correct 42 ms 68424 KB Output is correct
15 Correct 41 ms 68320 KB Output is correct
16 Correct 41 ms 68452 KB Output is correct
17 Correct 39 ms 68436 KB Output is correct
18 Correct 42 ms 68404 KB Output is correct
19 Correct 38 ms 68420 KB Output is correct
20 Correct 1361 ms 157672 KB Output is correct
21 Correct 1526 ms 183060 KB Output is correct
22 Correct 956 ms 160164 KB Output is correct
23 Correct 922 ms 153564 KB Output is correct
24 Correct 976 ms 160296 KB Output is correct
25 Correct 1520 ms 164632 KB Output is correct
26 Correct 1304 ms 171536 KB Output is correct
27 Correct 1705 ms 186016 KB Output is correct
28 Correct 1206 ms 147904 KB Output is correct
29 Correct 890 ms 143052 KB Output is correct
30 Correct 1740 ms 192880 KB Output is correct
31 Correct 707 ms 136816 KB Output is correct
32 Correct 652 ms 135440 KB Output is correct
33 Correct 635 ms 134180 KB Output is correct
34 Correct 615 ms 130996 KB Output is correct
35 Correct 658 ms 135956 KB Output is correct
36 Correct 65 ms 71748 KB Output is correct
37 Correct 315 ms 102756 KB Output is correct
38 Correct 561 ms 128868 KB Output is correct
39 Correct 581 ms 136588 KB Output is correct
40 Correct 774 ms 150196 KB Output is correct
41 Correct 600 ms 133864 KB Output is correct
42 Correct 623 ms 130052 KB Output is correct
43 Correct 188 ms 85588 KB Output is correct
44 Correct 1488 ms 178840 KB Output is correct
45 Correct 1906 ms 185124 KB Output is correct
46 Correct 2286 ms 210264 KB Output is correct
47 Correct 2440 ms 211912 KB Output is correct
48 Correct 2246 ms 204920 KB Output is correct
49 Correct 1172 ms 151580 KB Output is correct
50 Correct 875 ms 139652 KB Output is correct
51 Correct 1941 ms 197520 KB Output is correct
52 Correct 712 ms 147736 KB Output is correct
53 Correct 89 ms 76608 KB Output is correct
54 Correct 1879 ms 185260 KB Output is correct
55 Correct 1797 ms 210220 KB Output is correct
56 Correct 2497 ms 214372 KB Output is correct
57 Correct 1556 ms 184484 KB Output is correct
58 Correct 1613 ms 190076 KB Output is correct
59 Correct 1888 ms 211428 KB Output is correct
60 Correct 1554 ms 184480 KB Output is correct
61 Correct 1603 ms 190108 KB Output is correct
62 Correct 1235 ms 151224 KB Output is correct
63 Correct 228 ms 89112 KB Output is correct
64 Correct 1239 ms 179720 KB Output is correct
65 Correct 1169 ms 173812 KB Output is correct
66 Correct 847 ms 147068 KB Output is correct
67 Correct 1105 ms 168872 KB Output is correct
68 Correct 691 ms 136700 KB Output is correct
69 Correct 2397 ms 214924 KB Output is correct
70 Correct 1751 ms 210188 KB Output is correct
71 Correct 2195 ms 205380 KB Output is correct
72 Correct 1171 ms 153568 KB Output is correct
73 Correct 2045 ms 200160 KB Output is correct
74 Correct 651 ms 140064 KB Output is correct
75 Correct 648 ms 141104 KB Output is correct
76 Correct 722 ms 146976 KB Output is correct
77 Correct 880 ms 151384 KB Output is correct
78 Correct 751 ms 139392 KB Output is correct
79 Correct 546 ms 128896 KB Output is correct
80 Correct 582 ms 136508 KB Output is correct
81 Correct 775 ms 150192 KB Output is correct
82 Correct 595 ms 133800 KB Output is correct
83 Correct 626 ms 130004 KB Output is correct
84 Correct 180 ms 82776 KB Output is correct
85 Correct 1915 ms 189148 KB Output is correct
86 Correct 2797 ms 242288 KB Output is correct
87 Correct 236 ms 94648 KB Output is correct
88 Correct 313 ms 98508 KB Output is correct
89 Correct 248 ms 94652 KB Output is correct
90 Correct 96 ms 75776 KB Output is correct
91 Correct 43 ms 68672 KB Output is correct
92 Correct 99 ms 74764 KB Output is correct
93 Correct 872 ms 132228 KB Output is correct
94 Correct 220 ms 89528 KB Output is correct
95 Correct 1391 ms 184676 KB Output is correct
96 Correct 1166 ms 174532 KB Output is correct
97 Correct 828 ms 146848 KB Output is correct
98 Correct 1139 ms 168732 KB Output is correct
99 Correct 3204 ms 269068 KB Output is correct
100 Correct 2325 ms 213140 KB Output is correct
101 Correct 2580 ms 227712 KB Output is correct
102 Correct 1164 ms 153976 KB Output is correct
103 Correct 639 ms 137892 KB Output is correct
104 Correct 632 ms 141108 KB Output is correct
105 Correct 730 ms 145176 KB Output is correct
106 Correct 646 ms 142440 KB Output is correct
107 Correct 681 ms 141340 KB Output is correct
108 Correct 153 ms 79804 KB Output is correct
109 Correct 1787 ms 182516 KB Output is correct
110 Correct 1677 ms 208100 KB Output is correct
111 Correct 1589 ms 205276 KB Output is correct
112 Correct 815 ms 148216 KB Output is correct
113 Correct 837 ms 145084 KB Output is correct