oj.uz

답안 #574000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574000 2022-06-07T14:51:00 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 4000 ms 21448 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) 
{
	set<ll> em; set<ll>::iterator it3 = em.lower_bound(0); if(it3!=em.end()) {DEBUG(0);}
 	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4328 KB Output is correct
2 Correct 84 ms 6812 KB Output is correct
3 Correct 94 ms 8328 KB Output is correct
4 Correct 133 ms 16296 KB Output is correct
5 Correct 160 ms 21448 KB Output is correct
6 Correct 155 ms 18664 KB Output is correct
7 Correct 73 ms 13632 KB Output is correct
8 Correct 98 ms 18128 KB Output is correct
9 Correct 162 ms 20020 KB Output is correct
10 Correct 90 ms 19264 KB Output is correct
11 Correct 12 ms 5276 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 4328 KB Output is correct
2 Correct 84 ms 6812 KB Output is correct
3 Correct 94 ms 8328 KB Output is correct
4 Correct 133 ms 16296 KB Output is correct
5 Correct 160 ms 21448 KB Output is correct
6 Correct 155 ms 18664 KB Output is correct
7 Correct 73 ms 13632 KB Output is correct
8 Correct 98 ms 18128 KB Output is correct
9 Correct 162 ms 20020 KB Output is correct
10 Correct 90 ms 19264 KB Output is correct
11 Correct 12 ms 5276 KB Output is correct
12 Correct 99 ms 8288 KB Output is correct
13 Correct 81 ms 15452 KB Output is correct
14 Correct 162 ms 20888 KB Output is correct
15 Correct 117 ms 15800 KB Output is correct
16 Correct 114 ms 15808 KB Output is correct
17 Correct 113 ms 15816 KB Output is correct
18 Correct 108 ms 15772 KB Output is correct
19 Correct 118 ms 15904 KB Output is correct
20 Correct 81 ms 13096 KB Output is correct
21 Execution timed out 4035 ms 10812 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -