Submission #290059

#	Time	Username	Problem	Language	Result	Execution time	Memory
290059		Mercenary	Sky Walking (IOI19_walk)	C++14	0 / 100	4083 ms	12920 KiB

walk

#ifndef LOCAL
#include "walk.h"
#endif // LOCAL
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
int n , m;
struct IT{
    ll s[maxn * 4];
    void update(int x , int l , int r , int pos , ll val){
        if(l == r){
            s[x] = val;return;
        }
        int mid = l + r >> 1;
        if(pos <= mid)update(x * 2 , l , mid , pos , val);
        else update(x * 2 + 1 , mid + 1 , r , pos , val);
        s[x] = min(s[x * 2] , s[x * 2 + 1]);
    }
    ll query(int x , int l , int r , int L , int R){
        if(l > R || L > r)return 1e18;
        if(L <= l && r <= R)return s[x];
        int mid = l + r >> 1;
        return min(query(x * 2 , l , mid , L , R) , query(x * 2 + 1 , mid + 1 , r , L , R));
    }
    void init(){
        fill_n(s,maxn*4,1e18);
    }
}s1 , s2;

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    n = x.size();m = l.size();
    s = 0 , g = n - 1;
    for(int i = 0 ; i < n ; ++i)h[i] = 1e9;
    vector<vector<int>> del(n , vector<int>(0));
    vector<vector<int>> add(n , vector<int>(0));
    vector<int> order(m);iota(order.begin(),order.end(),0);
    vector<int> id(m);
    sort(order.begin(),order.end(),[&](const int a , const int b){
            return y[a] < y[b];
         });
    for(int i = 0 ; i < m ; ++i)id[order[i]] = i;
    for(int i = 0 ; i < m ; ++i){
        add[l[i]].pb(i);
        del[r[i]].pb(i);
    }
    ll res = 1e18;
    s1.init();s2.init();
    set<int> ss;
    for(int i = 0 ; i < n ; ++i){
        if(i > 0){
            for(auto c : del[i - 1]){
                ss.erase(id[c]);
                auto it = lower_bound(ss.begin(),ss.end(),id[c]);
                auto update = [&](int c){
                    ll cur = min(s1.query(1,1,m,1,id[c]+1) + y[c], s2.query(1,1,m,id[c]+1,m)-y[c]);
                    s1.update(1,1,m,id[c]+1,min(s1.query(1,1,m,id[c]+1,id[c]+1),cur-y[c]));
                    s2.update(1,1,m,id[c]+1,min(s2.query(1,1,m,id[c]+1,id[c]+1),cur+y[c]));
                };
                if(it != ss.end())update(*it);
                if(it != ss.begin())update(*prev(it));
                s1.update(1,1,n,id[c]+1,1e18);
                s2.update(1,1,m,id[c]+1,1e18);
            }
        }
        for(auto c : add[i]){
            ll cur = min(s1.query(1,1,m,1,id[c]+1) + y[c], s2.query(1,1,m,id[c]+1,m)-y[c]);
            if(i == 0)cur = y[c];
            ss.insert(id[c]);
            s1.update(1,1,m,id[c]+1,cur-y[c]);
            s2.update(1,1,m,id[c]+1,cur+y[c]);
        }
    }
    for(auto c : del[n - 1]){
        ll cur = min(s1.query(1,1,m,1,id[c]+1) + y[c], s2.query(1,1,m,id[c]+1,m)-y[c]);
        res = min(res , cur + y[c]);
    }
    if(res > 1e15)res = -1;
    else res += x[n - 1] - x[0];
    return res;

}

#ifdef LOCAL
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    int n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<int> x(n), h(n);
	for (int i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<int> l(m), r(m), y(m);
	for (int i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	int s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
#endif // LOCAL

Compilation message (stderr)

walk.cpp: In member function 'void IT::update(int, int, int, int, ll)':
walk.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid = l + r >> 1;
      |                   ~~^~~
walk.cpp: In member function 'll IT::query(int, int, int, int, int)':
walk.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~

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