oj.uz

Submission #574016

# Submission time Handle Problem Language Result Execution time Memory
574016 2022-06-07T15:10:16 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 176 ms 18752 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});
	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()==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 3624 KB Output is correct
2 Correct 89 ms 5152 KB Output is correct
3 Correct 103 ms 6208 KB Output is correct
4 Correct 144 ms 13496 KB Output is correct
5 Correct 170 ms 18516 KB Output is correct
6 Correct 167 ms 15800 KB Output is correct
7 Correct 81 ms 10656 KB Output is correct
8 Correct 86 ms 15168 KB Output is correct
9 Correct 176 ms 17136 KB Output is correct
10 Correct 106 ms 16436 KB Output is correct
11 Correct 10 ms 4552 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3624 KB Output is correct
2 Correct 89 ms 5152 KB Output is correct
3 Correct 103 ms 6208 KB Output is correct
4 Correct 144 ms 13496 KB Output is correct
5 Correct 170 ms 18516 KB Output is correct
6 Correct 167 ms 15800 KB Output is correct
7 Correct 81 ms 10656 KB Output is correct
8 Correct 86 ms 15168 KB Output is correct
9 Correct 176 ms 17136 KB Output is correct
10 Correct 106 ms 16436 KB Output is correct
11 Correct 10 ms 4552 KB Output is correct
12 Correct 108 ms 6288 KB Output is correct
13 Correct 79 ms 13104 KB Output is correct
14 Correct 169 ms 18752 KB Output is correct
15 Correct 123 ms 13500 KB Output is correct
16 Correct 129 ms 13472 KB Output is correct
17 Correct 109 ms 13508 KB Output is correct
18 Correct 113 ms 13948 KB Output is correct
19 Correct 136 ms 14156 KB Output is correct
20 Correct 83 ms 11140 KB Output is correct
21 Correct 24 ms 8764 KB Output is correct
22 Incorrect 59 ms 11840 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 -