oj.uz

Submission #574009

# Submission time Handle Problem Language Result Execution time Memory
574009 2022-06-07T14:57:12 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 165 ms 18492 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 24 ms 3604 KB Output is correct
2 Correct 87 ms 5080 KB Output is correct
3 Correct 96 ms 6276 KB Output is correct
4 Correct 144 ms 13348 KB Output is correct
5 Correct 165 ms 18424 KB Output is correct
6 Correct 158 ms 15808 KB Output is correct
7 Correct 66 ms 10692 KB Output is correct
8 Correct 84 ms 15168 KB Output is correct
9 Correct 160 ms 17136 KB Output is correct
10 Correct 94 ms 16336 KB Output is correct
11 Correct 11 ms 4552 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3604 KB Output is correct
2 Correct 87 ms 5080 KB Output is correct
3 Correct 96 ms 6276 KB Output is correct
4 Correct 144 ms 13348 KB Output is correct
5 Correct 165 ms 18424 KB Output is correct
6 Correct 158 ms 15808 KB Output is correct
7 Correct 66 ms 10692 KB Output is correct
8 Correct 84 ms 15168 KB Output is correct
9 Correct 160 ms 17136 KB Output is correct
10 Correct 94 ms 16336 KB Output is correct
11 Correct 11 ms 4552 KB Output is correct
12 Correct 94 ms 6304 KB Output is correct
13 Correct 73 ms 13124 KB Output is correct
14 Correct 158 ms 18492 KB Output is correct
15 Correct 106 ms 13596 KB Output is correct
16 Correct 105 ms 13444 KB Output is correct
17 Correct 109 ms 13512 KB Output is correct
18 Correct 109 ms 13488 KB Output is correct
19 Correct 104 ms 13528 KB Output is correct
20 Correct 78 ms 10676 KB Output is correct
21 Correct 24 ms 8824 KB Output is correct
22 Incorrect 60 ms 11572 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 -