oj.uz

Submission #987231

# Submission time Handle Problem Language Result Execution time Memory
987231 2024-05-22T11:54:23 Z AdamGS Sky Walking (IOI19_walk) C++17
100 / 100
 2918 ms 229812 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
vector<ll>T, H;
vector<pair<ll,ll>>V[20*LIM];
set<pair<ll,ll>>S;
map<pair<ll,ll>,ll>mp;
ll tr[4*LIM], odl[20*LIM], n, N=1, akt;
void upd(int l, int r, ll x) {
  l+=N; r+=N;
  tr[l]=max(tr[l], x);
  tr[r]=max(tr[r], x);
  while(l/2!=r/2) {
    if(l%2==0) tr[l+1]=max(tr[l+1], x);
    if(r%2==1) tr[r-1]=max(tr[r-1], x);
    l/=2; r/=2;
  }
}
ll cnt(int v) {
  v+=N;
  ll ans=tr[v];
  while(v) {
    ans=max(ans, tr[v]);
    v/=2;
  }
  return ans;
}
void kraw(pair<ll,ll>a, pair<ll,ll>b) {
  if(mp.find(a)==mp.end()) {
    mp[a]=akt++;
    S.insert({a.nd, a.st});
  }
  if(mp.find(b)==mp.end()) {
    mp[b]=akt++;
    if(S.find({b.nd, b.st})==S.end() && b.nd!=0) {
      auto it=S.lower_bound({b.nd, b.st});
      if(it!=S.end()) {
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
      if(it!=S.begin()) {
        --it;
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
    }
    S.insert({b.nd, b.st});
  }
  ll o=abs(a.st-b.st)+abs(a.nd-b.nd);
  V[mp[a]].pb({mp[b], o});
  V[mp[b]].pb({mp[a], o});
}
void dodaj(ll l, ll r, ll y) {
  kraw({T[l], y}, {T[r], y});
  kraw({T[l], y}, {T[l], cnt(l)});
  kraw({T[r], y}, {T[r], cnt(r)});
  upd(l, r, y);
}
ll ind(vector<ll>&X, ll y) {
  ll po=0, ko=(ll)X.size()-1;
  while(po<ko) {
    ll sr=(po+ko+1)/2;
    if(H[X[sr]]>=y) po=sr; else ko=sr-1;
  }
  return X[po];
}
ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
  if(s>g) swap(s, g);
  n=x.size();
  T.resize(n);
  H.resize(n);
  rep(i, n) T[i]=x[i];
  rep(i, n) H[i]=h[i];
  while(N<n) N*=2;
  vector<pair<ll,pair<ll,ll>>>P;
  rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
  mp[{x[s], 0}]=0;
  mp[{x[g], 0}]=1;
  akt=2;
  sort(all(P));
  vector<ll>X, lewos, lewog, prawos, prawog;
  rep(i, n) {
    while(X.size()>0 && h[i]>=h[X.back()]) X.pop_back();
    X.pb(i);
    if(i==s) lewos=X;
    if(i==g) lewog=X;
  }
  X.clear();
  for(int i=n-1; i>=0; --i) {
    while(X.size()>0 && h[i]>=h[X.back()]) X.pop_back();
    X.pb(i);
    if(i==s) prawos=X;
    if(i==g) prawog=X;
  }
  for(auto i : P) {
    if(i.nd.nd<=s || g<=i.nd.st || s<=i.nd.st && i.nd.nd<=g) {
      dodaj(i.nd.st, i.nd.nd, i.st);
      continue;
    }
    ll a=i.nd.st, b=ind(lewos, i.st), c=ind(prawos, i.st), d=ind(lewog, i.st), e=ind(prawog, i.st), f=i.nd.nd;
    if(i.nd.nd<g) {
      dodaj(a, b, i.st);
      dodaj(b, c, i.st);
      dodaj(c, f, i.st);
      continue;
    }
    if(s<i.nd.st) {
      dodaj(a, d, i.st);
      dodaj(d, e, i.st);
      dodaj(e, f, i.st);
      continue;
    }
    dodaj(a, b, i.st);
    dodaj(b, c, i.st);
    if(c<d) dodaj(c, d, i.st);
    dodaj(d, e, i.st);
    dodaj(e, f, i.st);
  }
  rep(i, akt+1) odl[i]=INF;
  priority_queue<pair<ll,ll>>q;
  q.push({0, 0});
  while(!q.empty()) {
    ll o=-q.top().st, p=q.top().nd; q.pop();
    if(odl[p]<=o) continue;
    odl[p]=o;
    for(auto i : V[p]) q.push({-o-i.nd, i.st});
  }
  if(odl[1]==INF) return -1;
  return odl[1];
}

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:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
walk.cpp:84:3: note: in expansion of macro 'rep'
   84 |   rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
      |   ^~~
walk.cpp:104:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  104 |     if(i.nd.nd<=s || g<=i.nd.st || s<=i.nd.st && i.nd.nd<=g) {
      |                                    ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47196 KB Output is correct
2 Correct 33 ms 47304 KB Output is correct
3 Correct 27 ms 47408 KB Output is correct
4 Correct 30 ms 47180 KB Output is correct
5 Correct 30 ms 47452 KB Output is correct
6 Correct 27 ms 47440 KB Output is correct
7 Correct 29 ms 47468 KB Output is correct
8 Correct 32 ms 47444 KB Output is correct
9 Correct 30 ms 47196 KB Output is correct
10 Correct 30 ms 47448 KB Output is correct
11 Correct 31 ms 47348 KB Output is correct
12 Correct 28 ms 47452 KB Output is correct
13 Correct 30 ms 47188 KB Output is correct
14 Correct 25 ms 47652 KB Output is correct
15 Correct 28 ms 47196 KB Output is correct
16 Correct 31 ms 47448 KB Output is correct
17 Correct 31 ms 47440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47288 KB Output is correct
2 Correct 28 ms 47192 KB Output is correct
3 Correct 1202 ms 129880 KB Output is correct
4 Correct 1353 ms 139720 KB Output is correct
5 Correct 740 ms 118684 KB Output is correct
6 Correct 768 ms 121060 KB Output is correct
7 Correct 786 ms 119224 KB Output is correct
8 Correct 1439 ms 133460 KB Output is correct
9 Correct 1162 ms 134496 KB Output is correct
10 Correct 1385 ms 140180 KB Output is correct
11 Correct 1064 ms 122564 KB Output is correct
12 Correct 827 ms 118728 KB Output is correct
13 Correct 1457 ms 143052 KB Output is correct
14 Correct 685 ms 135268 KB Output is correct
15 Correct 675 ms 136244 KB Output is correct
16 Correct 513 ms 119752 KB Output is correct
17 Correct 547 ms 115748 KB Output is correct
18 Correct 570 ms 106176 KB Output is correct
19 Correct 62 ms 52452 KB Output is correct
20 Correct 420 ms 97996 KB Output is correct
21 Correct 502 ms 112380 KB Output is correct
22 Correct 553 ms 117860 KB Output is correct
23 Correct 687 ms 130504 KB Output is correct
24 Correct 547 ms 117452 KB Output is correct
25 Correct 551 ms 114160 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 68344 KB Output is correct
2 Correct 1420 ms 143816 KB Output is correct
3 Correct 1664 ms 146520 KB Output is correct
4 Correct 1595 ms 153096 KB Output is correct
5 Correct 1567 ms 159548 KB Output is correct
6 Correct 1513 ms 151656 KB Output is correct
7 Correct 688 ms 104240 KB Output is correct
8 Correct 701 ms 118564 KB Output is correct
9 Correct 1387 ms 149660 KB Output is correct
10 Correct 501 ms 111188 KB Output is correct
11 Correct 36 ms 50260 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 68344 KB Output is correct
2 Correct 1420 ms 143816 KB Output is correct
3 Correct 1664 ms 146520 KB Output is correct
4 Correct 1595 ms 153096 KB Output is correct
5 Correct 1567 ms 159548 KB Output is correct
6 Correct 1513 ms 151656 KB Output is correct
7 Correct 688 ms 104240 KB Output is correct
8 Correct 701 ms 118564 KB Output is correct
9 Correct 1387 ms 149660 KB Output is correct
10 Correct 501 ms 111188 KB Output is correct
11 Correct 36 ms 50260 KB Output is correct
12 Correct 1519 ms 146284 KB Output is correct
13 Correct 1128 ms 151240 KB Output is correct
14 Correct 1527 ms 158972 KB Output is correct
15 Correct 1165 ms 148936 KB Output is correct
16 Correct 1126 ms 140448 KB Output is correct
17 Correct 1125 ms 155180 KB Output is correct
18 Correct 1199 ms 148608 KB Output is correct
19 Correct 1093 ms 138156 KB Output is correct
20 Correct 707 ms 102864 KB Output is correct
21 Correct 58 ms 55004 KB Output is correct
22 Correct 892 ms 130924 KB Output is correct
23 Correct 864 ms 129184 KB Output is correct
24 Correct 608 ms 118216 KB Output is correct
25 Correct 820 ms 124812 KB Output is correct
26 Correct 565 ms 114916 KB Output is correct
27 Correct 1454 ms 159940 KB Output is correct
28 Correct 1234 ms 150276 KB Output is correct
29 Correct 1509 ms 151880 KB Output is correct
30 Correct 728 ms 104440 KB Output is correct
31 Correct 1367 ms 145776 KB Output is correct
32 Correct 495 ms 111924 KB Output is correct
33 Correct 478 ms 114628 KB Output is correct
34 Correct 609 ms 120172 KB Output is correct
35 Correct 663 ms 123076 KB Output is correct
36 Correct 562 ms 117832 KB Output is correct
37 Correct 510 ms 112232 KB Output is correct
38 Correct 565 ms 117808 KB Output is correct
39 Correct 696 ms 130332 KB Output is correct
40 Correct 514 ms 117132 KB Output is correct
41 Correct 525 ms 114116 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47196 KB Output is correct
2 Correct 33 ms 47304 KB Output is correct
3 Correct 27 ms 47408 KB Output is correct
4 Correct 30 ms 47180 KB Output is correct
5 Correct 30 ms 47452 KB Output is correct
6 Correct 27 ms 47440 KB Output is correct
7 Correct 29 ms 47468 KB Output is correct
8 Correct 32 ms 47444 KB Output is correct
9 Correct 30 ms 47196 KB Output is correct
10 Correct 30 ms 47448 KB Output is correct
11 Correct 31 ms 47348 KB Output is correct
12 Correct 28 ms 47452 KB Output is correct
13 Correct 30 ms 47188 KB Output is correct
14 Correct 25 ms 47652 KB Output is correct
15 Correct 28 ms 47196 KB Output is correct
16 Correct 31 ms 47448 KB Output is correct
17 Correct 31 ms 47440 KB Output is correct
18 Correct 29 ms 47288 KB Output is correct
19 Correct 28 ms 47192 KB Output is correct
20 Correct 1202 ms 129880 KB Output is correct
21 Correct 1353 ms 139720 KB Output is correct
22 Correct 740 ms 118684 KB Output is correct
23 Correct 768 ms 121060 KB Output is correct
24 Correct 786 ms 119224 KB Output is correct
25 Correct 1439 ms 133460 KB Output is correct
26 Correct 1162 ms 134496 KB Output is correct
27 Correct 1385 ms 140180 KB Output is correct
28 Correct 1064 ms 122564 KB Output is correct
29 Correct 827 ms 118728 KB Output is correct
30 Correct 1457 ms 143052 KB Output is correct
31 Correct 685 ms 135268 KB Output is correct
32 Correct 675 ms 136244 KB Output is correct
33 Correct 513 ms 119752 KB Output is correct
34 Correct 547 ms 115748 KB Output is correct
35 Correct 570 ms 106176 KB Output is correct
36 Correct 62 ms 52452 KB Output is correct
37 Correct 420 ms 97996 KB Output is correct
38 Correct 502 ms 112380 KB Output is correct
39 Correct 553 ms 117860 KB Output is correct
40 Correct 687 ms 130504 KB Output is correct
41 Correct 547 ms 117452 KB Output is correct
42 Correct 551 ms 114160 KB Output is correct
43 Correct 209 ms 68344 KB Output is correct
44 Correct 1420 ms 143816 KB Output is correct
45 Correct 1664 ms 146520 KB Output is correct
46 Correct 1595 ms 153096 KB Output is correct
47 Correct 1567 ms 159548 KB Output is correct
48 Correct 1513 ms 151656 KB Output is correct
49 Correct 688 ms 104240 KB Output is correct
50 Correct 701 ms 118564 KB Output is correct
51 Correct 1387 ms 149660 KB Output is correct
52 Correct 501 ms 111188 KB Output is correct
53 Correct 36 ms 50260 KB Output is correct
54 Correct 1519 ms 146284 KB Output is correct
55 Correct 1128 ms 151240 KB Output is correct
56 Correct 1527 ms 158972 KB Output is correct
57 Correct 1165 ms 148936 KB Output is correct
58 Correct 1126 ms 140448 KB Output is correct
59 Correct 1125 ms 155180 KB Output is correct
60 Correct 1199 ms 148608 KB Output is correct
61 Correct 1093 ms 138156 KB Output is correct
62 Correct 707 ms 102864 KB Output is correct
63 Correct 58 ms 55004 KB Output is correct
64 Correct 892 ms 130924 KB Output is correct
65 Correct 864 ms 129184 KB Output is correct
66 Correct 608 ms 118216 KB Output is correct
67 Correct 820 ms 124812 KB Output is correct
68 Correct 565 ms 114916 KB Output is correct
69 Correct 1454 ms 159940 KB Output is correct
70 Correct 1234 ms 150276 KB Output is correct
71 Correct 1509 ms 151880 KB Output is correct
72 Correct 728 ms 104440 KB Output is correct
73 Correct 1367 ms 145776 KB Output is correct
74 Correct 495 ms 111924 KB Output is correct
75 Correct 478 ms 114628 KB Output is correct
76 Correct 609 ms 120172 KB Output is correct
77 Correct 663 ms 123076 KB Output is correct
78 Correct 562 ms 117832 KB Output is correct
79 Correct 510 ms 112232 KB Output is correct
80 Correct 565 ms 117808 KB Output is correct
81 Correct 696 ms 130332 KB Output is correct
82 Correct 514 ms 117132 KB Output is correct
83 Correct 525 ms 114116 KB Output is correct
84 Correct 170 ms 64248 KB Output is correct
85 Correct 1784 ms 151660 KB Output is correct
86 Correct 2316 ms 191876 KB Output is correct
87 Correct 115 ms 63148 KB Output is correct
88 Correct 114 ms 61808 KB Output is correct
89 Correct 116 ms 63292 KB Output is correct
90 Correct 72 ms 53584 KB Output is correct
91 Correct 36 ms 47448 KB Output is correct
92 Correct 73 ms 51536 KB Output is correct
93 Correct 504 ms 88480 KB Output is correct
94 Correct 64 ms 55380 KB Output is correct
95 Correct 1008 ms 135236 KB Output is correct
96 Correct 907 ms 130500 KB Output is correct
97 Correct 743 ms 126148 KB Output is correct
98 Correct 850 ms 124680 KB Output is correct
99 Correct 2918 ms 229812 KB Output is correct
100 Correct 1521 ms 152124 KB Output is correct
101 Correct 2021 ms 178088 KB Output is correct
102 Correct 819 ms 104556 KB Output is correct
103 Correct 648 ms 111880 KB Output is correct
104 Correct 636 ms 114556 KB Output is correct
105 Correct 608 ms 118496 KB Output is correct
106 Correct 591 ms 123844 KB Output is correct
107 Correct 713 ms 131808 KB Output is correct
108 Correct 126 ms 56084 KB Output is correct
109 Correct 1173 ms 138072 KB Output is correct
110 Correct 1228 ms 149956 KB Output is correct
111 Correct 1153 ms 150724 KB Output is correct
112 Correct 671 ms 122028 KB Output is correct
113 Correct 657 ms 120312 KB Output is correct