| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1050529 | NotLinux | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "walk.h"
#define int long long
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 1e9 + 7;
const long long inf = 1e18 + 7;
struct Segt{// range add update , range min query , point set update
struct Node{
int left , right;
long long val , lzt;
Node():left(-1) , right(-1) , val(inf) , lzt(0ll){}
} dummy;
vector < Node > tree;
int create_node(){
tree.push_back(dummy);
return sz(tree) - 1;
}
Segt(){
tree.resize(1);
}
void push(int ind , int l , int r){
if(tree[ind].lzt){
tree[ind].val += tree[ind].lzt;
if(tree[ind].left == -1)tree[ind].left = create_node();
tree[tree[ind].left].lzt += tree[ind].lzt;
if(tree[ind].right == -1)tree[ind].right = create_node();
tree[tree[ind].right].lzt += tree[ind].lzt;
tree[ind].lzt = 0;
}
}
void set(int ind , int l , int r , int p , int v){
push(ind,l,r);
if(l == r){
tree[ind].val = v;
return;
}
int mid = (l + r) / 2;
if(tree[ind].left == -1)tree[ind].left = create_node();
if(tree[ind].right == -1)tree[ind].right = create_node();
if(mid >= p){
set(tree[ind].left , l , mid , p , v);
}
else{
set(tree[ind].right , mid+1 , r , p , v);
}
push(tree[ind].left , l , mid);
push(tree[ind].right , mid+1 , r);
tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
}
void set(int p , int v){
set(0 , 0 , N , p , v);
}
void add(int ind , int l , int r , int ql , int qr , int qv){
push(ind,l,r);
if(l >= ql and r <= qr){
tree[ind].lzt += qv;
push(ind,l,r);
return;
}
else if(l > qr or r < ql){
return;
}
int mid = (l + r) / 2;
if(tree[ind].left == -1)tree[ind].left = create_node();
if(tree[ind].right == -1)tree[ind].right = create_node();
add(tree[ind].left , l , mid , ql , qr , qv);
add(tree[ind].right , mid+1 , r , ql , qr , qv);
tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
}
void add(int l , int r , int v){
add(0 , 0 , N , l , r , v);
}
int query(int ind , int l , int r , int ql , int qr){
if(ind == -1)return inf;
push(ind,l,r);
if(l >= ql and r <= qr){
return tree[ind].val;
}
else if(l > qr or r < ql)return inf;
else{
int mid = (l + r) / 2;
return min(query(tree[ind].left , l , mid , ql , qr) , query(tree[ind].right , mid+1 , r , ql , qr));
}
}
int query(int l , int r){
return query(0 , 0 , N , l , r);
}
};
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
vector < int > range_start[sz(X)] , range_end[sz(X)];
for(int i = 0;i<sz(L);i++){
range_start[L[i]].push_back(i);
range_end[R[i]].push_back(i);
}
Segt segt_top , segt_down;
segt_top.set(0 , 0);
segt_down.set(0 , 0);
int ans = inf;
for(int i = 0;i<sz(X);i++){
set < int > fuck;
vector < int > make_updates;
for(auto itr : range_start[i]){
// cout << "STARTED : " << L[itr] << " , " << R[itr] << " , " << Y[itr] << endl;
fuck.insert(Y[itr]);
int min_distance = min(segt_top.query(Y[itr] , H[i]) - Y[itr], segt_down.query(0 , Y[itr]) + Y[itr]);
// cout << "min_distance : " << min_distance << endl;
make_updates.push_back(min_distance);
}
for(int j = 0;j<sz(range_start[i]);j++){
segt_top.set(Y[range_start[i][j]] , make_updates[j] + Y[range_start[i][j]]);
segt_down.set(Y[range_start[i][j]] , make_updates[j] - Y[range_start[i][j]]);
}
if(i != (sz(X)-1)){
for(auto itr : range_end[i]){
if(fuck.count(Y[itr]) == 0){
// cout << "ENDED : " << L[itr] << " , " << R[itr] << endl;
segt_top.set(Y[itr] , inf);
segt_down.set(Y[itr] , inf);
}
}
}
if(i == 0){
segt_top.set(0 , inf);
segt_down.set(0 , inf);
}
if(i != (sz(X)-1)){
segt_top.add(1 , N , X[i+1] - X[i]);
segt_down.add(1 , N , X[i+1] - X[i]);
}
// cout << "Segt : ";for(int i = 0;i<=10;i++)cout << segt_top.query(i,i) << " ";cout << endl;
// cout << X[i] << " : " << segt_top.query(0 , N) << endl;
// if(segt_top.query(0 , N) >= inf){
// cout << "stop : " << X[i] << endl;
// return 0ll;
// }
}
int ret = segt_top.query(0 , H[sz(H) - 1]);
if(ret < inf)return ret;
else return -1;
}