oj.uz

Submission #932364

# Submission time Handle Problem Language Result Execution time Memory
932364 2024-02-23T08:51:14 Z beepbeepsheep Sky Walking (IOI19_walk) C++17
0 / 100
 316 ms 68544 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<3>(a)<get<3>(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];
			//cerr<<a<<' '<<b<<' '<<c<<' '<<d<<" queries"<<endl;
			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);
				//cerr<<c<<' '<<hi<<' '<<lo<<' '<<res<<endl;
				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
	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 600 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 20820 KB Output is correct
2 Correct 316 ms 38964 KB Output is correct
3 Correct 262 ms 43184 KB Output is correct
4 Correct 284 ms 66868 KB Output is correct
5 Correct 303 ms 67088 KB Output is correct
6 Correct 270 ms 67784 KB Output is correct
7 Correct 117 ms 47560 KB Output is correct
8 Correct 221 ms 66176 KB Output is correct
9 Correct 229 ms 66620 KB Output is correct
10 Correct 167 ms 68544 KB Output is correct
11 Incorrect 21 ms 14428 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 20820 KB Output is correct
2 Correct 316 ms 38964 KB Output is correct
3 Correct 262 ms 43184 KB Output is correct
4 Correct 284 ms 66868 KB Output is correct
5 Correct 303 ms 67088 KB Output is correct
6 Correct 270 ms 67784 KB Output is correct
7 Correct 117 ms 47560 KB Output is correct
8 Correct 221 ms 66176 KB Output is correct
9 Correct 229 ms 66620 KB Output is correct
10 Correct 167 ms 68544 KB Output is correct
11 Incorrect 21 ms 14428 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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