Submission #763838

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
763838	2023-06-22 23:56:52	NK_	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1875 ms	61988 KiB

Main

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>
using namespace std;
#define nl '\n'
using ll = long long;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N; cin >> N;
  vector<array<int, 2>> A(N);
  for(auto& x : A) {
    cin >> x[0] >> x[1];
  }
  set<int> S; for(int i = 0; i < N; i++) S.insert(i);
  vector<int> IDX; for(int i = 0; i < N; i++) IDX.push_back(i);
  for(int t = 0; t < 2; t++) {
    sort(begin(IDX), end(IDX), [&](int x, int y) {
      if (A[x] == A[y]) return x < y;
      return A[x] < A[y];
    }); 
    vector<int> stk = {-1};
    for(auto i : IDX) {
      while(stk.back() != -1 && (A[stk.back()][1] - A[stk.back()][0]) <= (A[i][1] - A[i][0])) {
        stk.pop_back();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31