oj.uz

Submission #574008

# Submission time Handle Problem Language Result Execution time Memory
574008 2022-06-07T14:56:35 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 163 ms 18872 KB 
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) 
{
 	ll N = x.size(); ll M = l.size();
	vector<vector<ll> > be,en; VV(be,N,{}); VV(en,N,{});
	REP(i,0,M) {be[l[i]].pb(y[i]); en[r[i]].pb(y[i]);}
	be[N-1].pb(0); en[0].pb(0); 
	set<pl> active; //{height,min_dist} 
	active.insert({0LL,0LL}); active.insert({-1LL,INF});
	set<pl>::iterator under,over; ll d_under,d_over;
	ll he,L; vector<pl> newval;
	REP(i,0,N)
	{
		newval.clear();
		REP(j,0,be[i].size())
		{
			he=be[i][j]; L=h[i];
			under = active.lower_bound({he,0LL}); if(under==active.begin()) {d_under=INF;} else {under--; d_under=he-under->ff + under->ss;}
			over = active.lower_bound({he,0LL}); if(over==active.end() || over->ff>L) {d_over=INF;} else{d_over=over->ff-he+over->ss;}
			if(min<ll>(d_over,d_under)<INF) {newval.pb({he,min<ll>(d_over,d_under)});}
		}
		REP(j,0,en[i].size())
		{
			if(active.lower_bound({en[i][j],0LL})==active.end()) {continue;}
			active.erase(active.lower_bound({en[i][j],0LL}));
		}
		REP(j,0,newval.size()) {active.insert(newval[j]);}
 	}
	if(active.size()==1) {return -1LL;} else {return ((++active.begin())->ss + x[N-1]-x[0]);}
}

Compilation message

walk.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
walk.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 23 ms 3544 KB Output is correct
2 Correct 87 ms 5148 KB Output is correct
3 Correct 95 ms 6292 KB Output is correct
4 Correct 144 ms 13448 KB Output is correct
5 Correct 160 ms 18528 KB Output is correct
6 Correct 157 ms 15680 KB Output is correct
7 Correct 66 ms 10636 KB Output is correct
8 Correct 94 ms 15284 KB Output is correct
9 Correct 163 ms 17144 KB Output is correct
10 Correct 89 ms 16348 KB Output is correct
11 Correct 12 ms 4552 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3544 KB Output is correct
2 Correct 87 ms 5148 KB Output is correct
3 Correct 95 ms 6292 KB Output is correct
4 Correct 144 ms 13448 KB Output is correct
5 Correct 160 ms 18528 KB Output is correct
6 Correct 157 ms 15680 KB Output is correct
7 Correct 66 ms 10636 KB Output is correct
8 Correct 94 ms 15284 KB Output is correct
9 Correct 163 ms 17144 KB Output is correct
10 Correct 89 ms 16348 KB Output is correct
11 Correct 12 ms 4552 KB Output is correct
12 Correct 95 ms 6308 KB Output is correct
13 Correct 73 ms 13108 KB Output is correct
14 Correct 161 ms 18872 KB Output is correct
15 Correct 107 ms 13408 KB Output is correct
16 Correct 111 ms 13740 KB Output is correct
17 Correct 106 ms 13480 KB Output is correct
18 Correct 114 ms 13928 KB Output is correct
19 Correct 108 ms 13880 KB Output is correct
20 Correct 73 ms 11080 KB Output is correct
21 Correct 27 ms 8764 KB Output is correct
22 Incorrect 62 ms 13904 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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