oj.uz

답안 #735788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
735788 2023-05-04T16:30:59 Z Sam_a17 Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 183276 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;

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 38284 KB Output is correct
2 Correct 20 ms 38304 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 19 ms 38344 KB Output is correct
5 Correct 20 ms 38388 KB Output is correct
6 Correct 18 ms 38288 KB Output is correct
7 Correct 20 ms 38384 KB Output is correct
8 Correct 24 ms 38328 KB Output is correct
9 Correct 24 ms 38348 KB Output is correct
10 Correct 18 ms 37896 KB Output is correct
11 Correct 21 ms 38292 KB Output is correct
12 Correct 21 ms 38320 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 38284 KB Output is correct
2 Correct 20 ms 38304 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 19 ms 38344 KB Output is correct
5 Correct 20 ms 38388 KB Output is correct
6 Correct 18 ms 38288 KB Output is correct
7 Correct 20 ms 38384 KB Output is correct
8 Correct 24 ms 38328 KB Output is correct
9 Correct 24 ms 38348 KB Output is correct
10 Correct 18 ms 37896 KB Output is correct
11 Correct 21 ms 38292 KB Output is correct
12 Correct 21 ms 38320 KB Output is correct
13 Correct 43 ms 40020 KB Output is correct
14 Correct 42 ms 40096 KB Output is correct
15 Correct 27 ms 40060 KB Output is correct
16 Correct 46 ms 40164 KB Output is correct
17 Correct 41 ms 40152 KB Output is correct
18 Correct 36 ms 40192 KB Output is correct
19 Correct 36 ms 40112 KB Output is correct
20 Correct 37 ms 40096 KB Output is correct
21 Correct 31 ms 40148 KB Output is correct
22 Correct 36 ms 40148 KB Output is correct
23 Correct 47 ms 40124 KB Output is correct
24 Correct 39 ms 40148 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 662 ms 166296 KB Output is correct
2 Correct 654 ms 166172 KB Output is correct
3 Correct 730 ms 167920 KB Output is correct
4 Correct 637 ms 165588 KB Output is correct
5 Correct 822 ms 180060 KB Output is correct
6 Correct 777 ms 178856 KB Output is correct
7 Correct 788 ms 183276 KB Output is correct
8 Correct 725 ms 169216 KB Output is correct
9 Correct 718 ms 169492 KB Output is correct
10 Correct 797 ms 178852 KB Output is correct
11 Correct 965 ms 178852 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1829 ms 168124 KB Output is correct
2 Execution timed out 2061 ms 180800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2064 ms 181952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 38284 KB Output is correct
2 Correct 20 ms 38304 KB Output is correct
3 Correct 20 ms 38356 KB Output is correct
4 Correct 19 ms 38344 KB Output is correct
5 Correct 20 ms 38388 KB Output is correct
6 Correct 18 ms 38288 KB Output is correct
7 Correct 20 ms 38384 KB Output is correct
8 Correct 24 ms 38328 KB Output is correct
9 Correct 24 ms 38348 KB Output is correct
10 Correct 18 ms 37896 KB Output is correct
11 Correct 21 ms 38292 KB Output is correct
12 Correct 21 ms 38320 KB Output is correct
13 Correct 43 ms 40020 KB Output is correct
14 Correct 42 ms 40096 KB Output is correct
15 Correct 27 ms 40060 KB Output is correct
16 Correct 46 ms 40164 KB Output is correct
17 Correct 41 ms 40152 KB Output is correct
18 Correct 36 ms 40192 KB Output is correct
19 Correct 36 ms 40112 KB Output is correct
20 Correct 37 ms 40096 KB Output is correct
21 Correct 31 ms 40148 KB Output is correct
22 Correct 36 ms 40148 KB Output is correct
23 Correct 47 ms 40124 KB Output is correct
24 Correct 39 ms 40148 KB Output is correct
25 Correct 662 ms 166296 KB Output is correct
26 Correct 654 ms 166172 KB Output is correct
27 Correct 730 ms 167920 KB Output is correct
28 Correct 637 ms 165588 KB Output is correct
29 Correct 822 ms 180060 KB Output is correct
30 Correct 777 ms 178856 KB Output is correct
31 Correct 788 ms 183276 KB Output is correct
32 Correct 725 ms 169216 KB Output is correct
33 Correct 718 ms 169492 KB Output is correct
34 Correct 797 ms 178852 KB Output is correct
35 Correct 965 ms 178852 KB Output is correct
36 Correct 1829 ms 168124 KB Output is correct
37 Execution timed out 2061 ms 180800 KB Time limit exceeded
38 Halted 0 ms 0 KB -