제출 #1254011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254011		jwvg0425	장애물 (IOI25_obstacles)	C++20	0 / 100	2093 ms	5808 KiB

obstacles

#include "obstacles.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

vector<int> t, h;

void initialize(vector<int> T, vector<int> H)
{
	t = T;
	h = H;
}

void expand(int& l, int& r, int& minh, int v)
{
	while (l > 0 && h[l - 1] < v)
	{
		l--;
		minh = min(minh, h[l]);
	}

	while (r + 1 < t.size() && h[r + 1] < v)
	{
		r++;
		minh = max(minh, h[r]);
	}
}

bool can_reach(int l, int r, int s, int d)
{
	int sl = s, sr = s;
	int mins = h[s];
	int dl = d, dr = d;
	int mind = h[d];
	int maxt = t[0] - 1;

	
	for (int y = 0; y < h.size(); y++)
	{
		// 잠기면 끝
		if (mins >= t[y] || mind >= t[y])
			return false;

		// 아니면 가능한 한 확장
		if (t[y] > maxt)
		{
			maxt = t[y];
			expand(sl, sr, mins, t[y]);
			expand(dl, dr, mind, t[y]);
		}

		// 확장한 구간이 겹치면 끝
		int l = max(sl, dl);
		int r = min(sr, dr);

		if (l <= r)
			return true;
	}

	return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17