oj.uz

Submission #623092

# Submission time Handle Problem Language Result Execution time Memory
623092 2022-08-05T07:26:15 Z slime Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 10960 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 998244353;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
long long fib[MAXN], lucas[MAXN];
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); 
  lucas[0] = 2;
  lucas[1] = 1;
  for(int i=2; i<MAXN; i++) lucas[i] = (lucas[i-2] + lucas[i-1]) % MOD;
  fib[0] = 0;
  fib[1] = 1;
  for(int i=2; i<MAXN; i++) fib[i] = (fib[i-2] + fib[i-1]) % MOD;
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void google(int i) { cout << "Case #" << i << ": "; }
int csb(int l, int r, int k) { // count number of [l, r] such that i & 2^k > 0
  if(l > r) return 0;
  if(l == 0) {
    int s = r / (1ll << (k+1)); // number of complete cycles
    int t = r % (1ll << (k+1));
    int ans = s * (1ll << k);
    ans += (t >= (1ll << k) ? t - (1ll << k) + 1 : 0);
    return ans;
  }
  else return csb(0, r, k) - csb(0, l - 1, k);
}
int lis(vector<int> a) {
  int n = a.size();
  int bucket[n+1];
  for(int i=1; i<=n; i++) bucket[i] = 1e18;
  int ans = 1;
  for(int x: a) {
    auto it = lower_bound(bucket + 1, bucket +n +1, x);
    int d = distance(bucket, it);
    ans = max(ans, d);
    bucket[d] = min(bucket[d], x);
  }
  return ans;
}
void solve(int tc) {
  int n, q;
  cin >> n >> q;
  int s[n+1], e[n+1];
  for(int i=1; i<=n; i++) cin >> s[i] >> e[i];
  while(q--) {
    int x, y;
    cin >> x >> y;
    int ans = 0;
    if(x == y) {
      cout << "0\n";  continue;
    }
    bool done = 0;
    for(int i=1; i<=n; i++) {
      if(s[y] <= e[x] && e[x] <= e[y]) {
        cout << ans + 1 << "\n"; 
        done = 1;
        break;
      }
      int id = -1, mins = 1e18;
      for(int j=1; j<=n; j++) {
        if(s[j] < mins && s[y] <= e[j] && e[j] <= e[y]) {
          id = j; mins = s[j];
        }
      }
      if(id == -1) {
        cout << "impossible\n";
        done = 1;
        break;
      }
      y = id;
      ans++;
      if(id == x) {
        cout << i << "\n";
        done = 1;
        break;
      }
    }
    if(!done) cout << "impossible\n";
  }
} 
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

/*

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Execution timed out 1569 ms 10960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 242 ms 7384 KB Output is correct
4 Correct 156 ms 7388 KB Output is correct
5 Correct 130 ms 7380 KB Output is correct
6 Correct 145 ms 7384 KB Output is correct
7 Correct 64 ms 7384 KB Output is correct
8 Correct 68 ms 7380 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 242 ms 7384 KB Output is correct
4 Correct 156 ms 7388 KB Output is correct
5 Correct 130 ms 7380 KB Output is correct
6 Correct 145 ms 7384 KB Output is correct
7 Correct 64 ms 7384 KB Output is correct
8 Correct 68 ms 7380 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct
10 Correct 8 ms 7252 KB Output is correct
11 Correct 8 ms 7344 KB Output is correct
12 Correct 242 ms 7384 KB Output is correct
13 Correct 159 ms 7392 KB Output is correct
14 Correct 132 ms 7380 KB Output is correct
15 Correct 150 ms 7384 KB Output is correct
16 Correct 72 ms 7380 KB Output is correct
17 Correct 63 ms 7384 KB Output is correct
18 Correct 7 ms 7388 KB Output is correct
19 Execution timed out 1568 ms 7636 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 242 ms 7384 KB Output is correct
4 Correct 156 ms 7388 KB Output is correct
5 Correct 130 ms 7380 KB Output is correct
6 Correct 145 ms 7384 KB Output is correct
7 Correct 64 ms 7384 KB Output is correct
8 Correct 68 ms 7380 KB Output is correct
9 Correct 8 ms 7396 KB Output is correct
10 Correct 8 ms 7252 KB Output is correct
11 Correct 11 ms 7348 KB Output is correct
12 Correct 254 ms 7388 KB Output is correct
13 Correct 165 ms 7384 KB Output is correct
14 Correct 121 ms 7376 KB Output is correct
15 Correct 136 ms 7396 KB Output is correct
16 Correct 80 ms 7388 KB Output is correct
17 Correct 95 ms 7392 KB Output is correct
18 Correct 7 ms 7408 KB Output is correct
19 Execution timed out 1577 ms 10832 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Execution timed out 1569 ms 10960 KB Time limit exceeded
3 Halted 0 ms 0 KB -