oj.uz

Submission #210271

# Submission time Handle Problem Language Result Execution time Memory
210271 2020-03-17T01:11:10 Z Segtree Sky Walking (IOI19_walk) C++14
15 / 100
 234 ms 23348 KB 
#include"walk.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<stack>
#include<fstream>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
typedef struct st{
	ll height,eid;
	bool operator<(const st&key)const{
		if(this->height==key.height)return this->eid<key.eid;
		return this->height<key.height;
	}
	bool operator==(const st&key)const{
		return this->eid==key.eid;
	}
}st;
ll min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){
	int n=x.size(),m=l.size();
	set<st> S;
	S.insert((st){0,m});
	ll dp[100010];
	rep(i,m)dp[i]=1e17;
	dp[m]=0;
	vector<ll> app[100010],disapp[100010];
	rep(i,m){
		app[l[i]].push_back(i);
		disapp[r[i]].push_back(i);
	}
	disapp[0].push_back(m);
	rep(i,n){
		for(auto id:app[i])S.insert((st){y[id],id});
		for(auto id:disapp[i])S.erase((st){y[id],id});
		//cerr<<"S.size()="<<i<<" "<<S.size()<<endl;
		for(auto id:disapp[i]){
			auto it=S.lower_bound((st){y[id],id});
			if(it!=S.end()){
				//cerr<<"dp:"<<it->eid<<" "<<id<<endl;
				chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
			}
			if(it!=S.begin()){
				it--;
				//cerr<<"dp:"<<it->eid<<" "<<id<<endl;
				chmin(dp[it->eid],dp[id]+abs(y[id]-it->height));
			}
		}
	}
	ll ans=1e17;
	for(auto id:disapp[n-1])chmin(ans,dp[id]+y[id]);
	if(ans==1e17)return -1;
	ans+=x[n-1]-x[0];
	return ans;
}/*
int main(){
	int n,m,s,g;
	cin>>n>>m;
	vector<int> x(n),h(n),l(m),r(m),y(m);
	rep(i,n)cin>>x[i]>>h[i];
	rep(i,m)cin>>l[i]>>r[i]>>y[i];
	cin>>s>>g;
	cout<<min_distance(x,h,l,r,y,s,g)<<endl;
}*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8312 KB Output is correct
2 Correct 112 ms 12280 KB Output is correct
3 Correct 129 ms 13304 KB Output is correct
4 Correct 183 ms 18300 KB Output is correct
5 Correct 227 ms 23348 KB Output is correct
6 Correct 220 ms 20724 KB Output is correct
7 Correct 100 ms 14072 KB Output is correct
8 Correct 142 ms 19960 KB Output is correct
9 Correct 213 ms 21872 KB Output is correct
10 Correct 126 ms 20204 KB Output is correct
11 Correct 23 ms 6520 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8312 KB Output is correct
2 Correct 112 ms 12280 KB Output is correct
3 Correct 129 ms 13304 KB Output is correct
4 Correct 183 ms 18300 KB Output is correct
5 Correct 227 ms 23348 KB Output is correct
6 Correct 220 ms 20724 KB Output is correct
7 Correct 100 ms 14072 KB Output is correct
8 Correct 142 ms 19960 KB Output is correct
9 Correct 213 ms 21872 KB Output is correct
10 Correct 126 ms 20204 KB Output is correct
11 Correct 23 ms 6520 KB Output is correct
12 Correct 132 ms 13304 KB Output is correct
13 Correct 187 ms 18296 KB Output is correct
14 Correct 234 ms 23288 KB Output is correct
15 Correct 170 ms 18168 KB Output is correct
16 Correct 162 ms 18424 KB Output is correct
17 Correct 165 ms 18424 KB Output is correct
18 Correct 157 ms 18168 KB Output is correct
19 Correct 160 ms 18424 KB Output is correct
20 Correct 110 ms 14072 KB Output is correct
21 Incorrect 45 ms 8696 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -