oj.uz

답안 #573975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573975 2022-06-07T14:07:13 Z PedroBigMan Sky Walking (IOI19_walk) C++14
15 / 100
 4000 ms 18588 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 26 ms 3656 KB Output is correct
2 Correct 84 ms 5080 KB Output is correct
3 Correct 92 ms 6224 KB Output is correct
4 Correct 138 ms 13432 KB Output is correct
5 Correct 182 ms 18476 KB Output is correct
6 Correct 166 ms 15784 KB Output is correct
7 Correct 73 ms 10580 KB Output is correct
8 Correct 93 ms 15184 KB Output is correct
9 Correct 204 ms 17140 KB Output is correct
10 Correct 95 ms 16436 KB Output is correct
11 Correct 12 ms 4528 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3656 KB Output is correct
2 Correct 84 ms 5080 KB Output is correct
3 Correct 92 ms 6224 KB Output is correct
4 Correct 138 ms 13432 KB Output is correct
5 Correct 182 ms 18476 KB Output is correct
6 Correct 166 ms 15784 KB Output is correct
7 Correct 73 ms 10580 KB Output is correct
8 Correct 93 ms 15184 KB Output is correct
9 Correct 204 ms 17140 KB Output is correct
10 Correct 95 ms 16436 KB Output is correct
11 Correct 12 ms 4528 KB Output is correct
12 Correct 90 ms 6296 KB Output is correct
13 Correct 83 ms 13128 KB Output is correct
14 Correct 162 ms 18588 KB Output is correct
15 Correct 151 ms 13500 KB Output is correct
16 Correct 125 ms 13484 KB Output is correct
17 Correct 107 ms 13504 KB Output is correct
18 Correct 114 ms 13524 KB Output is correct
19 Correct 123 ms 13520 KB Output is correct
20 Correct 84 ms 10684 KB Output is correct
21 Execution timed out 4050 ms 8772 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 -