oj.uz

Submission #573967

# Submission time Handle Problem Language Result Execution time Memory
573967 2022-06-07T13:56:57 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 4000 ms 18512 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}));
		}
		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 3552 KB Output is correct
2 Correct 84 ms 5128 KB Output is correct
3 Correct 99 ms 6292 KB Output is correct
4 Correct 132 ms 13428 KB Output is correct
5 Correct 159 ms 18388 KB Output is correct
6 Correct 162 ms 15864 KB Output is correct
7 Correct 77 ms 10792 KB Output is correct
8 Correct 98 ms 15140 KB Output is correct
9 Correct 154 ms 17080 KB Output is correct
10 Correct 86 ms 16328 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 26 ms 3552 KB Output is correct
2 Correct 84 ms 5128 KB Output is correct
3 Correct 99 ms 6292 KB Output is correct
4 Correct 132 ms 13428 KB Output is correct
5 Correct 159 ms 18388 KB Output is correct
6 Correct 162 ms 15864 KB Output is correct
7 Correct 77 ms 10792 KB Output is correct
8 Correct 98 ms 15140 KB Output is correct
9 Correct 154 ms 17080 KB Output is correct
10 Correct 86 ms 16328 KB Output is correct
11 Correct 12 ms 4552 KB Output is correct
12 Correct 92 ms 6200 KB Output is correct
13 Correct 75 ms 12992 KB Output is correct
14 Correct 174 ms 18512 KB Output is correct
15 Correct 135 ms 13452 KB Output is correct
16 Correct 122 ms 13532 KB Output is correct
17 Correct 108 ms 13496 KB Output is correct
18 Correct 111 ms 13520 KB Output is correct
19 Correct 104 ms 13536 KB Output is correct
20 Correct 74 ms 10564 KB Output is correct
21 Execution timed out 4074 ms 8772 KB Time limit exceeded
22 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 -