oj.uz

Submission #735789

# Submission time Handle Problem Language Result Execution time Memory
735789 2023-05-04T16:32:34 Z Sam_a17 Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 158552 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;

    int ina = 0, inb = n, ans = -2;
    pair<long long, long long> pr;
    while(ina <= inb) {
      int mid = (ina + inb) / 2;
      pr = {l[s], r[s]};

      for(int j = 0; j < LOG; j++) {
        if(mid & (1 << j)) {
          auto uu = seg_max[j].qry(pr.first, pr.second + 1);
          pr.first = min(pr.first, uu.first);
          pr.second = max(pr.second, uu.second);
        }
      }

      if(t >= pr.first && t <= pr.second) {
        ans = mid;
        inb = mid - 1;
      } else {
        ina = mid + 1;
      }
    }

    cout << ans + 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 20 ms 38184 KB Output is correct
3 Correct 19 ms 38292 KB Output is correct
4 Correct 24 ms 38300 KB Output is correct
5 Correct 19 ms 38300 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38288 KB Output is correct
8 Correct 21 ms 38300 KB Output is correct
9 Correct 20 ms 38204 KB Output is correct
10 Correct 19 ms 37820 KB Output is correct
11 Correct 20 ms 38176 KB Output is correct
12 Correct 21 ms 38240 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 20 ms 38184 KB Output is correct
3 Correct 19 ms 38292 KB Output is correct
4 Correct 24 ms 38300 KB Output is correct
5 Correct 19 ms 38300 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38288 KB Output is correct
8 Correct 21 ms 38300 KB Output is correct
9 Correct 20 ms 38204 KB Output is correct
10 Correct 19 ms 37820 KB Output is correct
11 Correct 20 ms 38176 KB Output is correct
12 Correct 21 ms 38240 KB Output is correct
13 Correct 43 ms 39636 KB Output is correct
14 Correct 44 ms 39636 KB Output is correct
15 Correct 25 ms 39688 KB Output is correct
16 Correct 45 ms 39716 KB Output is correct
17 Correct 42 ms 39656 KB Output is correct
18 Correct 37 ms 39764 KB Output is correct
19 Correct 34 ms 39740 KB Output is correct
20 Correct 36 ms 39752 KB Output is correct
21 Correct 25 ms 39676 KB Output is correct
22 Correct 33 ms 39764 KB Output is correct
23 Correct 37 ms 39736 KB Output is correct
24 Correct 41 ms 39636 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 142712 KB Output is correct
2 Correct 586 ms 142544 KB Output is correct
3 Correct 643 ms 144124 KB Output is correct
4 Correct 556 ms 142052 KB Output is correct
5 Correct 775 ms 155032 KB Output is correct
6 Correct 650 ms 153864 KB Output is correct
7 Correct 717 ms 158552 KB Output is correct
8 Correct 602 ms 145352 KB Output is correct
9 Correct 606 ms 145656 KB Output is correct
10 Correct 681 ms 153740 KB Output is correct
11 Correct 687 ms 153864 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1890 ms 144084 KB Output is correct
2 Execution timed out 2070 ms 155192 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 156244 KB Time limit exceeded
2 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 20 ms 38184 KB Output is correct
3 Correct 19 ms 38292 KB Output is correct
4 Correct 24 ms 38300 KB Output is correct
5 Correct 19 ms 38300 KB Output is correct
6 Correct 20 ms 38228 KB Output is correct
7 Correct 20 ms 38288 KB Output is correct
8 Correct 21 ms 38300 KB Output is correct
9 Correct 20 ms 38204 KB Output is correct
10 Correct 19 ms 37820 KB Output is correct
11 Correct 20 ms 38176 KB Output is correct
12 Correct 21 ms 38240 KB Output is correct
13 Correct 43 ms 39636 KB Output is correct
14 Correct 44 ms 39636 KB Output is correct
15 Correct 25 ms 39688 KB Output is correct
16 Correct 45 ms 39716 KB Output is correct
17 Correct 42 ms 39656 KB Output is correct
18 Correct 37 ms 39764 KB Output is correct
19 Correct 34 ms 39740 KB Output is correct
20 Correct 36 ms 39752 KB Output is correct
21 Correct 25 ms 39676 KB Output is correct
22 Correct 33 ms 39764 KB Output is correct
23 Correct 37 ms 39736 KB Output is correct
24 Correct 41 ms 39636 KB Output is correct
25 Correct 582 ms 142712 KB Output is correct
26 Correct 586 ms 142544 KB Output is correct
27 Correct 643 ms 144124 KB Output is correct
28 Correct 556 ms 142052 KB Output is correct
29 Correct 775 ms 155032 KB Output is correct
30 Correct 650 ms 153864 KB Output is correct
31 Correct 717 ms 158552 KB Output is correct
32 Correct 602 ms 145352 KB Output is correct
33 Correct 606 ms 145656 KB Output is correct
34 Correct 681 ms 153740 KB Output is correct
35 Correct 687 ms 153864 KB Output is correct
36 Correct 1890 ms 144084 KB Output is correct
37 Execution timed out 2070 ms 155192 KB Time limit exceeded
38 Halted 0 ms 0 KB -