oj.uz

Submission #573968

# Submission time Handle Problem Language Result Execution time Memory
573968 2022-06-07T13:58:47 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 168 ms 18496 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 10000000000000000LL
#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});
	set<pl>::iterator under,over; ll d_under,d_over;
	ll he,L; vector<pl> newval;
	REP(i,0,N)
	{
		if(active.size()==0) {break;}
		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())
		{
			active.erase(active.lower_bound({en[i][j],0LL}));
			if(active.size()==0) {break;}
		}
		REP(j,0,newval.size()) {active.insert(newval[j]);}
	}
	if(active.size()==0) {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 26 ms 3588 KB Output is correct
2 Correct 80 ms 5148 KB Output is correct
3 Correct 89 ms 6296 KB Output is correct
4 Correct 128 ms 13364 KB Output is correct
5 Correct 168 ms 18496 KB Output is correct
6 Correct 150 ms 15800 KB Output is correct
7 Correct 66 ms 10564 KB Output is correct
8 Correct 89 ms 15176 KB Output is correct
9 Correct 159 ms 17224 KB Output is correct
10 Correct 90 ms 16368 KB Output is correct
11 Correct 11 ms 4528 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3588 KB Output is correct
2 Correct 80 ms 5148 KB Output is correct
3 Correct 89 ms 6296 KB Output is correct
4 Correct 128 ms 13364 KB Output is correct
5 Correct 168 ms 18496 KB Output is correct
6 Correct 150 ms 15800 KB Output is correct
7 Correct 66 ms 10564 KB Output is correct
8 Correct 89 ms 15176 KB Output is correct
9 Correct 159 ms 17224 KB Output is correct
10 Correct 90 ms 16368 KB Output is correct
11 Correct 11 ms 4528 KB Output is correct
12 Correct 86 ms 6240 KB Output is correct
13 Correct 69 ms 13104 KB Output is correct
14 Correct 150 ms 18492 KB Output is correct
15 Correct 105 ms 13612 KB Output is correct
16 Correct 112 ms 13500 KB Output is correct
17 Correct 118 ms 13512 KB Output is correct
18 Correct 117 ms 13408 KB Output is correct
19 Correct 104 ms 13508 KB Output is correct
20 Correct 80 ms 10696 KB Output is correct
21 Correct 27 ms 8756 KB Output is correct
22 Incorrect 84 ms 15272 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 -