제출 #850035

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
850035	2023-09-15 16:27:39	IBory	Bitaro's travel (JOI23_travel)	C++17	100 / 100	916 ms	18520 KiB

travel

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int SZ = 1 << 18;
ll X[SZ], LR[SZ], RL[SZ], pre[SZ];
// LR[n]: L 방향으로 가는데, 만약 출발 위치가 LR[n] 이하이면 반드시 오른쪽으로 꺾어야 한다
pii Merge(pii& a, pii& b) {
  return { min(a.first, b.first), max(a.second, b.second) };
}
struct Seg {
  pii T[SZ << 1];
  void Build() {
    for (int i = SZ; i > 0; --i) {
      T[i] = Merge(T[i * 2], T[i * 2 + 1]);
    }
  }
  pii Query(int L, int R) {
    pii ret = { 2e9, -2e9 };
    for (L += SZ - 1, R += SZ - 1; L <= R; L >>= 1, R >>= 1) {
      if (L & 1) ret = Merge(ret, T[L++]);
      if (!(R & 1)) ret = Merge(ret, T[R--]);
    }
    return ret;
  }
} T;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55