oj.uz

Submission #685628

# Submission time Handle Problem Language Result Execution time Memory
685628 2023-01-24T17:16:31 Z cadmiumsky Sky Walking (IOI19_walk) C++14
25 / 100
 1740 ms 231008 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<ll,ll>;
//using tii = tuple<int,int,int>;

struct tii {
  int first, second, ind;
  tii(int x, int y, int i) : first(x), second(y), ind(i) {;}
  tii() : first(-1), second(-1), ind(-1) {;}
  bool operator == (const tii& x) const { 
    return first == x.first && second == x.second;
  }
};


const int nmax = 1e5 + 5;
const ll inf = 1e18 + 5;

map<int, vector<pii>, greater<int>> segm;
map<int, vector<int>, greater<int>> columns;
vector<pii> buildings;

void repair(vector<pii> &v) {
  sort(all(v));
  int last = 0;
  for(int i = 1; i < sz(v); i++) {
    if(v[i].second == v[i + 1].first) {
      v[last].second = v[i + 1].second;
      v[i + 1].second = -1;
    }
    else
      last = i;
  }
  v.resize(distance(v.begin(), stable_partition(all(v), [](auto x) { return x.second != -1; })));
}

namespace PointsG {
  vector<tii> pts;
  vector<vector<pii>> g;
  
  void addedge(int x, int y, int w) {
    //cerr << x << ' ' << y << " - " << w << '\n';
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }
  void add(int x, int y) {
    //cerr << "+ " << x << ' ' << y< '\n';
    pts.emplace_back(x, y, sz(pts));
  }

  void init() {
    sort(all(pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
    pts.resize(distance(pts.begin(), unique(all(pts))));
    for(int i = 0; i < sz(pts); i++)
      pts[i].ind = i;
    g.resize(sz(pts));
    for(int l = 0; l < sz(pts);) {
      int r = l;
      while(r < sz(pts) && pts[r].first == pts[l].first)
        r++;
      //cerr << l << ' ' << r << ' ' << pts[l].first << '\n';
      for(int j = l + 1; j < r; j++)
        if(pts[j].second <= buildings[pts[l].first].second)
          addedge(pts[j].ind, pts[j - 1].ind, pts[j].second - pts[j - 1].second);
      l = r;
    }
    
    sort(all(pts), [](auto a, auto b) { return pii{a.second, a.first} < pii{b.second, b.first}; });
    for(int l = 0; l < sz(pts);) {
      int r = l;
      while(r < sz(pts) && pts[r].second == pts[l].second)
        r++;
      auto v = segm[pts[l].second];
      repair(v);
      int ptr = 0;
      for(int j = l + 1; j < r; j++) {
        while(ptr < sz(v) && v[ptr].second < pts[j].first) ptr++;
        if(ptr == sz(v)) break;
        if(v[ptr].first > pts[j].first) continue;
        if(v[ptr].first <= pts[j - 1].first) {
          addedge(pts[j].ind, pts[j - 1].ind, buildings[pts[j].first].first - buildings[pts[j - 1].first].first);
        }
      }
      l = r;
    }
    
  }
  
  ll start(int S = -1, int T = -1) {
    sort(all(pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
    for(auto [a, b, i] : pts) {
      if(b == 0) {
        if(S == -1) S = i;
        else T = i;
      }
      //cerr << a << ' ' << b << ' ' << i << '\n';
    }
    cerr << sz(pts) << '\n';
    vector<ll> arriv(sz(pts), inf);
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.emplace(0, S);
    arriv[S] = 0;
    //cerr << S << ' ' << T << ' ' << pts[S].first << ' ' << pts[S].second << '\n';
    //cerr <<  pts[T].first << ' ' << pts[T].second << '\n';
    //cerr << "Mogus\n";
    //exit(0);
    //int cnt = 0;
    while(!heap.empty()) {
      //cnt++;
      //if(cnt % 10000 == 0)
        //cerr << "Mogus\n";
    
      auto [c, node] = heap.top();
      heap.pop();
      if(c > arriv[node]) continue;
      //cerr << node << ' ' << c << '\n';
      for(auto [x, e] : g[node]) {
        if(e + c < arriv[x]) {
          arriv[x] = e + c;
          heap.emplace(e + c, x);
        }
      }
    }
    return arriv[T];
  }
}

namespace Beats {
  int r[nmax];
  int atr[nmax];
  set<int> segm;
  //#warning Gamble
  void split(int p, int y, bool add = 1) { // inutil? 
    
    //return;
    if(add)
      PointsG::add(p, y);
    
    auto it = segm.upper_bound(p);
    if(it != segm.begin() && !segm.empty()) {
      it = prev(it);
      int l = *it;
      //cerr << y << ": " << l << ' ' << p << ' ' << r[l] << ' ' << add << '\n';
      
      if(add && l <= p && p <= r[l])
        PointsG::add(p, atr[l]);
      if(l < p && p < r[l]) { // p nu se afla printre aia
        segm.insert(p + 1);
        r[p + 1] = r[l];
        r[l] = p - 1;
        atr[p + 1] = atr[l];
      }
      else if(l == p && p == r[l]) {
        segm.erase(p);
      }
      else if(l == p) {
        atr[p + 1] = atr[l];
        segm.insert(p + 1);
        r[p + 1] = r[l];
        segm.erase(l);
      }
      else if(p == r[l]) r[l]--;
    }
    if(add == 0) {
      r[p] = p;
      atr[p] = y;
      segm.insert(p);
    }
  }
  
  void color(int l, int R, int y) {
    
    //cerr << "\t" << l << ' ' << R << ' ' << y << '\n';
    split(l, y, 1);
    split(R, y, 1);
    auto it = segm.lower_bound(l);
    while(it != segm.end() && *it <= R) {
      //cerr << '\t' << *it << ' ' << r[*it] << '\n';
      PointsG::add(*it, y);
      PointsG::add(*it, atr[*it]);
      PointsG::add(r[*it], y);
      PointsG::add(r[*it], atr[*it]);
      segm.erase(it);
      it = segm.lower_bound(l);
    }
    segm.insert(l);
    r[l] = R;
    atr[l] = y;
    //cerr << "\t------\n";
    return;
  }
}

void initpoints() {
  for(auto &[y, v] : segm) {
    //for(auto a : columns[y])
      //Beats::split(a, y, 0);
    for(auto [l, r] : v)
      Beats::color(l, r, y);
  }
  return;
}

long long min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) {
  
  PointsG::add(s, 0);
  PointsG::add(g, 0);
  PointsG::pts.reserve(sz(l) * 8);
  PointsG::g.reserve(sz(l) * 8);
  
  for(int i = 0; i < sz(l); i++) {
    segm[y[i]].emplace_back(l[i], r[i]);
    if(l[i] <= s && s <= r[i])
      PointsG::add(s, y[i]);
    if(l[i] <= g && g <= r[i])
      PointsG::add(g, y[i]);
  }
  buildings.reserve(sz(x));
  for(int i = 0; i < sz(x); i++) {
    buildings.emplace_back(x[i], h[i]);
    columns[h[i]].emplace_back(i);
  }
  
  
  initpoints();
  
  
  //int o = 0;
  //sort(all(PointsG::pts), [](auto a, auto b) { return pii{a.first, a.second} < pii{b.first, b.second}; });
  //PointsG::pts.resize(distance(PointsG::pts.begin(), unique(all(PointsG::pts))));
  //cerr << PointsG::pts.size() << '\n';
  //for(auto [x, y, i] : PointsG::pts) {
    //cerr << buildings[x].first << ' ' << y << '\n';
  //}
  //return 69;
  
  PointsG::init();
  auto a = PointsG::start();
  if(a == inf) return -1;
  return a;
}
#undef int

/**
      Vom spune că toamna a venit... foarte trist -
-- George Bacovia, Scântei galbene
*/

Compilation message

walk.cpp: In function 'll PointsG::start(ll, ll)':
walk.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |     for(auto [a, b, i] : pts) {
      |              ^
walk.cpp:120:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |       auto [c, node] = heap.top();
      |            ^
walk.cpp:124:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |       for(auto [x, e] : g[node]) {
      |                ^
walk.cpp: In function 'void initpoints()':
walk.cpp:202:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  202 |   for(auto &[y, v] : segm) {
      |             ^
walk.cpp:205:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  205 |     for(auto [l, r] : v)
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 826 ms 121592 KB Output is correct
4 Correct 932 ms 134900 KB Output is correct
5 Correct 606 ms 114524 KB Output is correct
6 Correct 575 ms 109268 KB Output is correct
7 Correct 600 ms 114820 KB Output is correct
8 Correct 926 ms 138472 KB Output is correct
9 Correct 762 ms 126400 KB Output is correct
10 Incorrect 1049 ms 157024 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16072 KB Output is correct
2 Correct 1204 ms 189868 KB Output is correct
3 Correct 1578 ms 209892 KB Output is correct
4 Correct 1632 ms 221936 KB Output is correct
5 Correct 1668 ms 222260 KB Output is correct
6 Correct 1535 ms 207144 KB Output is correct
7 Correct 804 ms 116560 KB Output is correct
8 Correct 364 ms 49440 KB Output is correct
9 Correct 1401 ms 191752 KB Output is correct
10 Correct 357 ms 73656 KB Output is correct
11 Correct 11 ms 3660 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16072 KB Output is correct
2 Correct 1204 ms 189868 KB Output is correct
3 Correct 1578 ms 209892 KB Output is correct
4 Correct 1632 ms 221936 KB Output is correct
5 Correct 1668 ms 222260 KB Output is correct
6 Correct 1535 ms 207144 KB Output is correct
7 Correct 804 ms 116560 KB Output is correct
8 Correct 364 ms 49440 KB Output is correct
9 Correct 1401 ms 191752 KB Output is correct
10 Correct 357 ms 73656 KB Output is correct
11 Correct 11 ms 3660 KB Output is correct
12 Correct 1404 ms 208372 KB Output is correct
13 Correct 1279 ms 228324 KB Output is correct
14 Correct 1740 ms 230824 KB Output is correct
15 Correct 1004 ms 132016 KB Output is correct
16 Correct 992 ms 152428 KB Output is correct
17 Correct 1195 ms 174028 KB Output is correct
18 Correct 1026 ms 132108 KB Output is correct
19 Correct 988 ms 152240 KB Output is correct
20 Correct 780 ms 122720 KB Output is correct
21 Correct 77 ms 19596 KB Output is correct
22 Correct 930 ms 167756 KB Output is correct
23 Correct 778 ms 150076 KB Output is correct
24 Correct 553 ms 97408 KB Output is correct
25 Correct 718 ms 139524 KB Output is correct
26 Correct 436 ms 80700 KB Output is correct
27 Correct 1629 ms 231008 KB Output is correct
28 Correct 1206 ms 223480 KB Output is correct
29 Correct 1497 ms 214908 KB Output is correct
30 Correct 816 ms 124996 KB Output is correct
31 Correct 1368 ms 199844 KB Output is correct
32 Correct 286 ms 58596 KB Output is correct
33 Correct 299 ms 61040 KB Output is correct
34 Correct 371 ms 77348 KB Output is correct
35 Incorrect 537 ms 90300 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 826 ms 121592 KB Output is correct
21 Correct 932 ms 134900 KB Output is correct
22 Correct 606 ms 114524 KB Output is correct
23 Correct 575 ms 109268 KB Output is correct
24 Correct 600 ms 114820 KB Output is correct
25 Correct 926 ms 138472 KB Output is correct
26 Correct 762 ms 126400 KB Output is correct
27 Incorrect 1049 ms 157024 KB Output isn't correct
28 Halted 0 ms 0 KB -