oj.uz

답안 #735800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735800 2023-05-04T16:47:59 Z Sam_a17 Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 1265 ms 184128 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10, LOG = 21;
multiset<int> to_add[N], to_erase[N];
multiset<int> add[N], rase[N];
int n, k, m, q, l[N], r[N];
pair<long long, long long> up[N][LOG];

// segment Tree Max
// Range Queries
struct segTree {
  vector<pair<long long, long long>> mTree;
  int size;

  void init(long long n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    mTree.assign(2 * size - 1, {INT64_MAX, INT64_MIN});
  }

  pair<long long, long long> combine(pair<long long, long long> a, pair<long long, long long> b) {
    return make_pair(min(a.first, b.first), max(a.second, b.second));
  }

  void upd(int u, long long li, long long ri, int x, int lx, int rx) { // set value at pos u
    if(rx - lx == 1) {
      mTree[x] = {li, ri};
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, li, ri, 2 * x + 1, lx, m);
    }else {
      upd(u, li, ri, 2 * x + 2, m, rx);
    }
    mTree[x] = combine(mTree[2 * x + 1], mTree[2 * x + 2]);
  }

  void upd(int u, long long li, long long ri) {
    upd(u, li, ri, 0, 0, size);
  }

  pair<long long, long long> qry (int l, int r, int x, int lx, int rx) { // range queries
    if(l >= rx || lx >= r) {
      return {INT64_MAX, INT64_MIN};
    }
    if(lx >= l && r >= rx) {
      return mTree[x];
    }

    int m = (rx + lx) / 2;
    auto s1 = qry(l, r, 2 * x + 1, lx, m);
    auto s2 = qry(l, r, 2 * x + 2, m, rx);
    return combine(s1, s2);
  }

  pair<long long, long long> qry(int l, int r) {
    return qry(l, r, 0, 0, size);
  }
};

segTree seg_max[LOG];

void solve_() {
  cin >> n >> k;

  cin >> m;

  for(int i = 0; i < LOG; i++) {
    seg_max[i].init(n + 3);
  }

  for(int i = 1; i <= m; i++) {
    int s, t; cin >> s >> t;

    if(s < t) {
      int tt = min(t - 1, s + k - 1);
      to_add[s].insert(t);
      to_erase[tt + 1].insert(t);
    } else {
      // s > t
      int tt = max(t + 1, s - k + 1);
      add[s].insert(t);
      rase[tt - 1].insert(t);
    }
  }

  multiset<int> curr;
  for(int i = 1; i <= n; i++) {
    for(auto j: to_add[i]) {
      curr.insert(j);
    }

    for(auto j: to_erase[i]) {
      curr.erase(curr.find(j));
    }


    if(!curr.empty()) {
      r[i] = max(i, *curr.rbegin());
    } else {
      r[i] = i;
    }
  }

  curr.clear();
  for(int i = n; i >= 1; i--) {
    for(auto j: add[i]) {
      curr.insert(j);
    }

    for(auto j: rase[i]) {
      curr.erase(curr.find(j));
    }

    if(!curr.empty()) {
      l[i] = min(i, *curr.begin());
    } else {
      l[i] = i;
    }
  }

  for(int i = 1; i <= n; i++) {
    up[i][0] = {l[i], r[i]};
    seg_max[0].upd(i, l[i], r[i]);
  }

  for(int j = 1; j < LOG; j++) {
    for(int i = 1; i <= n; i++) {
      up[i][j] = seg_max[j - 1].qry(up[i][j - 1].first, up[i][j - 1].second + 1);
      seg_max[j].upd(i, up[i][j].first, up[i][j].second);
    }
  }

  //
  cin >> q;
  for(int i = 1; i <= q; i++) {
    int s, t; cin >> s >> t;

    pair<long long, long long> pp;
    pp = {up[s][LOG - 1].first, up[s][LOG - 1].second};

    if(t >= pp.first && t <= pp.second) {
      int ans = 0;

      pair<long long, long long> pr;
      pr = {l[s], r[s]};

      if(t >= pr.first && t <= pr.second) {
        cout << 1 << '\n';
        continue;
      }

      for(int i = LOG - 1; i >= 0; i--) {
        auto go_up = seg_max[i].qry(pr.first, pr.second + 1);
        go_up.first = min(pr.first, go_up.first);
        go_up.second = max(pr.second, go_up.second);

        if(t >= go_up.first && t <= go_up.second) {
          continue;
        } else {
          ans += (1 << i);
          pr = go_up;
        }
      }

      cout << ans + 2 << '\n';
    } else {
      cout << -1 << '\n';
    }
  }
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38356 KB Output is correct
2 Correct 20 ms 38356 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 20 ms 38296 KB Output is correct
5 Correct 22 ms 38392 KB Output is correct
6 Correct 20 ms 38356 KB Output is correct
7 Correct 20 ms 38360 KB Output is correct
8 Correct 20 ms 38356 KB Output is correct
9 Correct 20 ms 38356 KB Output is correct
10 Correct 19 ms 37908 KB Output is correct
11 Correct 21 ms 38356 KB Output is correct
12 Correct 21 ms 38272 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38356 KB Output is correct
2 Correct 20 ms 38356 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 20 ms 38296 KB Output is correct
5 Correct 22 ms 38392 KB Output is correct
6 Correct 20 ms 38356 KB Output is correct
7 Correct 20 ms 38360 KB Output is correct
8 Correct 20 ms 38356 KB Output is correct
9 Correct 20 ms 38356 KB Output is correct
10 Correct 19 ms 37908 KB Output is correct
11 Correct 21 ms 38356 KB Output is correct
12 Correct 21 ms 38272 KB Output is correct
13 Correct 34 ms 40020 KB Output is correct
14 Correct 31 ms 40008 KB Output is correct
15 Correct 29 ms 40064 KB Output is correct
16 Correct 30 ms 40124 KB Output is correct
17 Correct 32 ms 40116 KB Output is correct
18 Correct 30 ms 40148 KB Output is correct
19 Correct 29 ms 40020 KB Output is correct
20 Correct 29 ms 40128 KB Output is correct
21 Correct 28 ms 40152 KB Output is correct
22 Correct 31 ms 40148 KB Output is correct
23 Correct 32 ms 40128 KB Output is correct
24 Correct 30 ms 40020 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 681 ms 165448 KB Output is correct
2 Correct 645 ms 165288 KB Output is correct
3 Correct 691 ms 166908 KB Output is correct
4 Correct 658 ms 164736 KB Output is correct
5 Correct 858 ms 177612 KB Output is correct
6 Correct 709 ms 176616 KB Output is correct
7 Correct 798 ms 181192 KB Output is correct
8 Correct 704 ms 167916 KB Output is correct
9 Correct 699 ms 168480 KB Output is correct
10 Correct 784 ms 176432 KB Output is correct
11 Correct 796 ms 176588 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 797 ms 166788 KB Output is correct
2 Correct 807 ms 177892 KB Output is correct
3 Correct 885 ms 167380 KB Output is correct
4 Correct 818 ms 181324 KB Output is correct
5 Correct 881 ms 178564 KB Output is correct
6 Correct 872 ms 178780 KB Output is correct
7 Correct 937 ms 176816 KB Output is correct
8 Correct 1069 ms 176840 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 871 ms 178988 KB Output is correct
2 Correct 1061 ms 167460 KB Output is correct
3 Correct 1018 ms 163904 KB Output is correct
4 Correct 897 ms 160680 KB Output is correct
5 Correct 764 ms 159008 KB Output is correct
6 Correct 821 ms 158540 KB Output is correct
7 Correct 740 ms 173724 KB Output is correct
8 Correct 20 ms 38356 KB Output is correct
9 Correct 30 ms 40096 KB Output is correct
10 Correct 922 ms 182188 KB Output is correct
11 Correct 936 ms 184128 KB Output is correct
12 Correct 944 ms 181968 KB Output is correct
13 Correct 940 ms 184004 KB Output is correct
14 Correct 21 ms 38356 KB Output is correct
15 Correct 35 ms 40228 KB Output is correct
16 Correct 785 ms 178856 KB Output is correct
17 Correct 1155 ms 179604 KB Output is correct
18 Correct 1095 ms 179472 KB Output is correct
19 Correct 1050 ms 179472 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 38356 KB Output is correct
2 Correct 20 ms 38356 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 20 ms 38296 KB Output is correct
5 Correct 22 ms 38392 KB Output is correct
6 Correct 20 ms 38356 KB Output is correct
7 Correct 20 ms 38360 KB Output is correct
8 Correct 20 ms 38356 KB Output is correct
9 Correct 20 ms 38356 KB Output is correct
10 Correct 19 ms 37908 KB Output is correct
11 Correct 21 ms 38356 KB Output is correct
12 Correct 21 ms 38272 KB Output is correct
13 Correct 34 ms 40020 KB Output is correct
14 Correct 31 ms 40008 KB Output is correct
15 Correct 29 ms 40064 KB Output is correct
16 Correct 30 ms 40124 KB Output is correct
17 Correct 32 ms 40116 KB Output is correct
18 Correct 30 ms 40148 KB Output is correct
19 Correct 29 ms 40020 KB Output is correct
20 Correct 29 ms 40128 KB Output is correct
21 Correct 28 ms 40152 KB Output is correct
22 Correct 31 ms 40148 KB Output is correct
23 Correct 32 ms 40128 KB Output is correct
24 Correct 30 ms 40020 KB Output is correct
25 Correct 681 ms 165448 KB Output is correct
26 Correct 645 ms 165288 KB Output is correct
27 Correct 691 ms 166908 KB Output is correct
28 Correct 658 ms 164736 KB Output is correct
29 Correct 858 ms 177612 KB Output is correct
30 Correct 709 ms 176616 KB Output is correct
31 Correct 798 ms 181192 KB Output is correct
32 Correct 704 ms 167916 KB Output is correct
33 Correct 699 ms 168480 KB Output is correct
34 Correct 784 ms 176432 KB Output is correct
35 Correct 796 ms 176588 KB Output is correct
36 Correct 797 ms 166788 KB Output is correct
37 Correct 807 ms 177892 KB Output is correct
38 Correct 885 ms 167380 KB Output is correct
39 Correct 818 ms 181324 KB Output is correct
40 Correct 881 ms 178564 KB Output is correct
41 Correct 872 ms 178780 KB Output is correct
42 Correct 937 ms 176816 KB Output is correct
43 Correct 1069 ms 176840 KB Output is correct
44 Correct 871 ms 178988 KB Output is correct
45 Correct 1061 ms 167460 KB Output is correct
46 Correct 1018 ms 163904 KB Output is correct
47 Correct 897 ms 160680 KB Output is correct
48 Correct 764 ms 159008 KB Output is correct
49 Correct 821 ms 158540 KB Output is correct
50 Correct 740 ms 173724 KB Output is correct
51 Correct 20 ms 38356 KB Output is correct
52 Correct 30 ms 40096 KB Output is correct
53 Correct 922 ms 182188 KB Output is correct
54 Correct 936 ms 184128 KB Output is correct
55 Correct 944 ms 181968 KB Output is correct
56 Correct 940 ms 184004 KB Output is correct
57 Correct 21 ms 38356 KB Output is correct
58 Correct 35 ms 40228 KB Output is correct
59 Correct 785 ms 178856 KB Output is correct
60 Correct 1155 ms 179604 KB Output is correct
61 Correct 1095 ms 179472 KB Output is correct
62 Correct 1050 ms 179472 KB Output is correct
63 Correct 970 ms 166136 KB Output is correct
64 Correct 1129 ms 168012 KB Output is correct
65 Correct 1035 ms 166476 KB Output is correct
66 Correct 898 ms 180720 KB Output is correct
67 Correct 1044 ms 179660 KB Output is correct
68 Correct 830 ms 179724 KB Output is correct
69 Correct 876 ms 181592 KB Output is correct
70 Correct 843 ms 179728 KB Output is correct
71 Correct 1265 ms 179848 KB Output is correct