oj.uz

Submission #932371

# Submission time Handle Problem Language Result Execution time Memory
932371 2024-02-23T08:55:14 Z beepbeepsheep Sky Walking (IOI19_walk) C++17
33 / 100
 304 ms 68404 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define iiii tuple<ll,ll,ll,ll>
const ll maxn=1e5+5;
const ll inf=1e15;
struct node{
	ll s,e,m,val;
	node *l,*r;
	node(ll _s, ll _e){
		s=_s,e=_e,m=(s+e)>>1,val=inf;
		if (s!=e) l=new node(s,m),r=new node(m+1,e);
	}
	void upd(ll x, ll v){
		if (s==e){
			val=v;
			return;
		}
		if (x>m) r->upd(x,v);
		else l->upd(x,v);
		val=min(l->val,r->val);
	}
	ll query(ll x, ll y){
		if (x<=s && e<=y) return val;
		if (x>m) return r->query(x,y);
		if (y<=m) return l->query(x,y);
		return min(l->query(x,y),r->query(x,y));
	}
}*small, *big;
vector<iiii> bridges;
bool cmp(iiii a, iiii b){
	if (get<2>(a)==get<2>(b)) return get<0>(a)>get<0>(b);
	return get<2>(a)<get<2>(b);
}

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) {
	ll n=x.size(),m=l.size();
	assert(s==0 && g==n-1);
	small=new node(1,n);
	big=new node(1,n);
	for (int i=0;i<m;i++) bridges.emplace_back(l[i],r[i],y[i],i);
	sort(bridges.begin(),bridges.end(),cmp); //sorted by height
	vector<iiii> queries; //time, off/on, where to toggle, original height
	for (int i=0;i<m;i++){
		ll a,b,c,d;
		tie(a,b,c,d)=bridges[i];
		queries.emplace_back(a,0,i+1,c);
		queries.emplace_back(b,1,i+1,c);
	}
	queries.emplace_back(0,1,0,0);
	sort(queries.begin(),queries.end());
	ll ptr=0;
	small=new node(0,m+5),big=new node(0,m+5);
	small->upd(0,0);
	for (int i=0;i<n-1;i++){
		while (ptr!=queries.size() && get<0>(queries[ptr])<=i){
			ll a,b,c,d;
			tie(a,d,b,c)=queries[ptr];
			if (d==0){
				ll lo=small->query(0,b-1)+c;
				ll hi=big->query(b+1,m+5)-c;
				ll res=min(lo,hi);
				small->upd(b,res-c); //get dominated
				big->upd(b,res+c); //dominated
			} else{
				small->upd(b,inf);
				big->upd(b,inf); //reset to sentinels
			}
			ptr++;
		}
	}
	ll ans=big->query(0,m+5); //0 is under everything
	if (ans==inf) return -1;
	return ans+x.back()-x.front();
}

Compilation message

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:57:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   while (ptr!=queries.size() && get<0>(queries[ptr])<=i){
      |          ~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20812 KB Output is correct
2 Correct 229 ms 39340 KB Output is correct
3 Correct 240 ms 40072 KB Output is correct
4 Correct 247 ms 64320 KB Output is correct
5 Correct 260 ms 64312 KB Output is correct
6 Correct 304 ms 64304 KB Output is correct
7 Correct 112 ms 45716 KB Output is correct
8 Correct 207 ms 65940 KB Output is correct
9 Correct 214 ms 65324 KB Output is correct
10 Correct 138 ms 64584 KB Output is correct
11 Correct 15 ms 13656 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 20812 KB Output is correct
2 Correct 229 ms 39340 KB Output is correct
3 Correct 240 ms 40072 KB Output is correct
4 Correct 247 ms 64320 KB Output is correct
5 Correct 260 ms 64312 KB Output is correct
6 Correct 304 ms 64304 KB Output is correct
7 Correct 112 ms 45716 KB Output is correct
8 Correct 207 ms 65940 KB Output is correct
9 Correct 214 ms 65324 KB Output is correct
10 Correct 138 ms 64584 KB Output is correct
11 Correct 15 ms 13656 KB Output is correct
12 Correct 225 ms 40508 KB Output is correct
13 Correct 282 ms 64832 KB Output is correct
14 Correct 259 ms 64956 KB Output is correct
15 Correct 175 ms 66640 KB Output is correct
16 Correct 178 ms 66332 KB Output is correct
17 Correct 163 ms 66796 KB Output is correct
18 Correct 167 ms 66944 KB Output is correct
19 Correct 197 ms 67748 KB Output is correct
20 Correct 111 ms 47680 KB Output is correct
21 Correct 31 ms 28500 KB Output is correct
22 Correct 173 ms 62040 KB Output is correct
23 Correct 226 ms 62748 KB Output is correct
24 Correct 162 ms 63024 KB Output is correct
25 Correct 165 ms 61364 KB Output is correct
26 Correct 155 ms 63568 KB Output is correct
27 Correct 254 ms 67888 KB Output is correct
28 Correct 241 ms 68404 KB Output is correct
29 Correct 241 ms 67896 KB Output is correct
30 Correct 110 ms 47632 KB Output is correct
31 Correct 235 ms 66552 KB Output is correct
32 Correct 140 ms 62260 KB Output is correct
33 Correct 145 ms 67652 KB Output is correct
34 Correct 148 ms 65724 KB Output is correct
35 Correct 147 ms 65332 KB Output is correct
36 Correct 153 ms 63132 KB Output is correct
37 Correct 136 ms 59696 KB Output is correct
38 Correct 149 ms 66524 KB Output is correct
39 Correct 125 ms 68268 KB Output is correct
40 Correct 137 ms 65156 KB Output is correct
41 Correct 150 ms 61360 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -