Submission #592650

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
592650	2022-07-09 12:06:07	Lucpp	Sky Walking (IOI19_walk)	C++17	24 / 100	4073 ms	220480 KiB

walk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
const ll INF = 1e18;
ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
  int n = (int)X.size(), m = (int)L.size();
  vector<vector<int>> sect(n, {0});
  vector<vector<pair<int, int>>> goL(n, {{-1, -1}}), goR(n, {{-1, -1}});
  vector<tuple<int, int, int>> bridge;
  for(int i = 0; i < m; i++) bridge.emplace_back(Y[i], L[i], R[i]);
  sort(bridge.begin(), bridge.end());
  vector<pair<int, int>> tower;
  for(int i = 0; i < n; i++) tower.emplace_back(H[i], i);
  sort(tower.begin(), tower.end());
  set<int> active;
  for(int i = 0; i < n; i++) active.insert(i);
  int j = 0;
  for(auto [y, l, r] : bridge){
    while(j < n && tower[j].first < y) active.erase(tower[j++].second);
    auto it = active.find(l);
    int last = -1;
    while(it != active.end() && *it <= r){
      sect[*it].push_back(y);
      goL[*it].push_back({-1, -1});
      goR[*it].push_back({-1, -1});
      if(last != -1) goR[last].back() = {*it, sz(sect[*it])-1}, goL[*it].back() = {last, sz(sect[last])-1};
      last = *it;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43