oj.uz

Submission #735269

# Submission time Handle Problem Language Result Execution time Memory
735269 2023-05-03T19:45:04 Z Sam_a17 Railway Trip 2 (JOI22_ho_t4) C++17
35 / 100
 2000 ms 62980 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];
int n, k, m, q, r[N];
int up[N][LOG];

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

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

  pair<long long, long long> combine(pair<long long, long long> a, pair<long long, long long> b) {
    if(a.first > b.first) {
      return a;
    } else {
      return b;
    }
  }

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

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

  void upd(int u, long long v) {
    upd(u, v, 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_MIN, -1};
    }
    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;

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

  cin >> m;
  seg_max.init(n + 1);
  for(int i = 1; i <= m; i++) {
    int s, t; cin >> s >> t;
    int tt = min(t - 1, s + k - 1);
    to_add[s].insert(t);
    to_erase[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;
    }
    seg_max.upd(i, r[i]);
  }

  for(int i = n; i >= 1; i--) {
    if(r[i] > i) {
      auto it = seg_max.qry(i + 1, r[i] + 1);
      up[i][0] = it.second;
    } else {
      up[i][0] = i;
    } 
  }

  for(int j = 1; j < LOG; j++) {
    for(int i = 1; i <= n; i++) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }

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

    int ina = 0, inb = n, ans = -1;
    while(ina <= inb) {
      int mid = (ina + inb) / 2;

      int ss = s;
      for(int j = 0; j < LOG; j++) {
        if(mid & (1 << j)) {
          ss = up[ss][j];
        }
      }

      if(!ss) {
        inb = mid - 1;
        continue;
      }

      if(r[ss] >= t) {
        ans = mid;
        inb = mid - 1;
      } else {
        ina = mid + 1;
      }
    }

    if(ans == -1) {
      cout << -1 << '\n';
      continue;
    }

    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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 19156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 19156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 31800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 62980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 55920 KB Output is correct
2 Correct 259 ms 43184 KB Output is correct
3 Correct 291 ms 37868 KB Output is correct
4 Correct 140 ms 34680 KB Output is correct
5 Correct 127 ms 33048 KB Output is correct
6 Correct 100 ms 32596 KB Output is correct
7 Correct 181 ms 47728 KB Output is correct
8 Correct 11 ms 19148 KB Output is correct
9 Correct 13 ms 19596 KB Output is correct
10 Correct 339 ms 56220 KB Output is correct
11 Correct 366 ms 58104 KB Output is correct
12 Correct 375 ms 56236 KB Output is correct
13 Correct 371 ms 57972 KB Output is correct
14 Correct 12 ms 19112 KB Output is correct
15 Correct 14 ms 19540 KB Output is correct
16 Correct 224 ms 52912 KB Output is correct
17 Correct 335 ms 53676 KB Output is correct
18 Correct 323 ms 53632 KB Output is correct
19 Correct 305 ms 53660 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2088 ms 19156 KB Time limit exceeded
2 Halted 0 ms 0 KB -