oj.uz

Submission #735799

# Submission time Handle Problem Language Result Execution time Memory
735799 2023-05-04T16:47:11 Z Sam_a17 Railway Trip 2 (JOI22_ho_t4) C++17
52 / 100
 896 ms 161112 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 = 17;
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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38228 KB Output is correct
2 Correct 23 ms 38228 KB Output is correct
3 Correct 20 ms 38232 KB Output is correct
4 Correct 23 ms 38232 KB Output is correct
5 Correct 21 ms 38288 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38216 KB Output is correct
8 Correct 20 ms 38264 KB Output is correct
9 Correct 20 ms 38184 KB Output is correct
10 Correct 20 ms 37908 KB Output is correct
11 Correct 22 ms 38260 KB Output is correct
12 Correct 20 ms 38228 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38228 KB Output is correct
2 Correct 23 ms 38228 KB Output is correct
3 Correct 20 ms 38232 KB Output is correct
4 Correct 23 ms 38232 KB Output is correct
5 Correct 21 ms 38288 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38216 KB Output is correct
8 Correct 20 ms 38264 KB Output is correct
9 Correct 20 ms 38184 KB Output is correct
10 Correct 20 ms 37908 KB Output is correct
11 Correct 22 ms 38260 KB Output is correct
12 Correct 20 ms 38228 KB Output is correct
13 Correct 39 ms 39700 KB Output is correct
14 Correct 31 ms 39636 KB Output is correct
15 Correct 27 ms 39636 KB Output is correct
16 Correct 27 ms 39752 KB Output is correct
17 Correct 30 ms 39744 KB Output is correct
18 Correct 28 ms 39764 KB Output is correct
19 Correct 31 ms 39636 KB Output is correct
20 Correct 28 ms 39708 KB Output is correct
21 Correct 27 ms 39656 KB Output is correct
22 Correct 28 ms 39764 KB Output is correct
23 Correct 31 ms 39712 KB Output is correct
24 Correct 29 ms 39636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 142716 KB Output is correct
2 Correct 551 ms 142544 KB Output is correct
3 Correct 586 ms 144076 KB Output is correct
4 Correct 547 ms 142044 KB Output is correct
5 Correct 759 ms 155108 KB Output is correct
6 Correct 615 ms 153856 KB Output is correct
7 Correct 702 ms 158556 KB Output is correct
8 Correct 649 ms 145356 KB Output is correct
9 Correct 676 ms 145652 KB Output is correct
10 Correct 678 ms 153860 KB Output is correct
11 Correct 721 ms 153928 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 143964 KB Output is correct
2 Correct 742 ms 155232 KB Output is correct
3 Correct 826 ms 146300 KB Output is correct
4 Correct 713 ms 161112 KB Output is correct
5 Correct 784 ms 158744 KB Output is correct
6 Correct 762 ms 158912 KB Output is correct
7 Correct 864 ms 156876 KB Output is correct
8 Correct 896 ms 156876 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 156352 KB Output is correct
2 Incorrect 815 ms 146532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38228 KB Output is correct
2 Correct 23 ms 38228 KB Output is correct
3 Correct 20 ms 38232 KB Output is correct
4 Correct 23 ms 38232 KB Output is correct
5 Correct 21 ms 38288 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38216 KB Output is correct
8 Correct 20 ms 38264 KB Output is correct
9 Correct 20 ms 38184 KB Output is correct
10 Correct 20 ms 37908 KB Output is correct
11 Correct 22 ms 38260 KB Output is correct
12 Correct 20 ms 38228 KB Output is correct
13 Correct 39 ms 39700 KB Output is correct
14 Correct 31 ms 39636 KB Output is correct
15 Correct 27 ms 39636 KB Output is correct
16 Correct 27 ms 39752 KB Output is correct
17 Correct 30 ms 39744 KB Output is correct
18 Correct 28 ms 39764 KB Output is correct
19 Correct 31 ms 39636 KB Output is correct
20 Correct 28 ms 39708 KB Output is correct
21 Correct 27 ms 39656 KB Output is correct
22 Correct 28 ms 39764 KB Output is correct
23 Correct 31 ms 39712 KB Output is correct
24 Correct 29 ms 39636 KB Output is correct
25 Correct 598 ms 142716 KB Output is correct
26 Correct 551 ms 142544 KB Output is correct
27 Correct 586 ms 144076 KB Output is correct
28 Correct 547 ms 142044 KB Output is correct
29 Correct 759 ms 155108 KB Output is correct
30 Correct 615 ms 153856 KB Output is correct
31 Correct 702 ms 158556 KB Output is correct
32 Correct 649 ms 145356 KB Output is correct
33 Correct 676 ms 145652 KB Output is correct
34 Correct 678 ms 153860 KB Output is correct
35 Correct 721 ms 153928 KB Output is correct
36 Correct 696 ms 143964 KB Output is correct
37 Correct 742 ms 155232 KB Output is correct
38 Correct 826 ms 146300 KB Output is correct
39 Correct 713 ms 161112 KB Output is correct
40 Correct 784 ms 158744 KB Output is correct
41 Correct 762 ms 158912 KB Output is correct
42 Correct 864 ms 156876 KB Output is correct
43 Correct 896 ms 156876 KB Output is correct
44 Correct 794 ms 156352 KB Output is correct
45 Incorrect 815 ms 146532 KB Output isn't correct
46 Halted 0 ms 0 KB -