oj.uz

Submission #647379

# Submission time Handle Problem Language Result Execution time Memory
647379 2022-10-02T10:39:40 Z Pety Event Hopping (BOI22_events) C++14
30 / 100
 160 ms 14728 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, q, E[100002], dp[20][100002], ind[100002];
pair<int, int>p[100002];
int aint[400002], poz[400002];

void build (int nod, int st, int dr) {
  aint[nod] = INF;
  poz[nod] = st;
  if (st < dr) {
    build(2 * nod, st, (st + dr) / 2);
    build(2 * nod + 1, (st + dr) / 2 + 1, dr);
  }
}

void update (int nod, int st, int dr, int x, pair<int, int> val) {
  if (st == dr) {
    if (aint[nod] > val.first) {
      aint[nod] = val.first;
      poz[nod] = val.second;
    }
    return;
  }
  int mid = (st + dr) / 2;
  if (x <= mid)
    update(2 * nod, st, mid, x, val);
  else
    update(2 * nod + 1, mid + 1, dr, x, val);
  aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
  if (aint[2 * nod] == aint[nod])
    poz[nod] = poz[2 * nod];
  else
    poz[nod] = poz[2 * nod + 1];
}

pair<int, int> query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) 
    return {aint[nod], poz[nod]};
  int mid = (st + dr) / 2;
  if (b <= mid)
    return query(2 * nod, st, mid, a, b);
  else if (a > mid)
    return query(2 * nod + 1, mid + 1, dr, a, b);
  else {
    auto p1 = query(2 * nod, st, mid, a, b);
    auto p2 = query(2 * nod + 1, mid + 1, dr, a, b);
    return min(p1, p2);
  }
}

bool cmp (int a, int b) {
  if (p[a].second == p[b].second)
    return p[a].first < p[b].first;
  return p[a].second < p[b].second;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].first >> p[i].second;
    E[i] = p[i].second;
  }
  sort(E + 1, E + n + 1);
  int m = 0;
  for (int i = 1; i <= n; i++) {
    ind[i] = i;
    if (i == 1 || E[i] != E[i - 1])
      E[++m] = E[i];
  }
  sort(ind + 1, ind + n + 1, cmp);
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    p[ind[i]].second = lower_bound(E + 1, E + m + 1, p[ind[i]].second) - E;
    p[ind[i]].first = lower_bound(E + 1, E + m + 1, p[ind[i]].first) - E;
    update(1, 1, n, p[ind[i]].second, {p[ind[i]].first, ind[i]});
    dp[0][ind[i]] = query(1, 1, n, p[ind[i]].first, p[ind[i]].second).second; 
  }

  int lim = 0;
  while ((1 << lim) <= m)
    lim++;
  lim--;
  for (int i = 1; (1 << i) <= m; i++) 
    for (int j = 1; j <= m; j++)
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
  while (q--) {
    int s, e;
    cin >> s >> e;
    if (p[e].second < p[s].second) {
      cout << "impossible\n";
      continue;
    }
    if (p[s].second >= p[e].first) {
      cout<< (s != e) << "\n";
      continue;
    }
    
    int ans = 0;
    for (int i = lim; i >= 0; i--) {
      if (p[s].second < p[dp[i][e]].first) {
        e = dp[i][e];
        ans += (1 << i);
      }
    }
    e = dp[0][e];
    ans++;
    if (p[e].first <= p[s].second) 
      cout << ans + (s != e) << "\n";
    else
      cout << "impossible\n";
  }
  
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 100 ms 14236 KB Output is correct
3 Correct 114 ms 14304 KB Output is correct
4 Correct 160 ms 14200 KB Output is correct
5 Correct 122 ms 14548 KB Output is correct
6 Correct 118 ms 14360 KB Output is correct
7 Incorrect 121 ms 14600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 31 ms 2308 KB Output is correct
20 Correct 33 ms 2308 KB Output is correct
21 Incorrect 32 ms 2692 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 504 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 74 ms 12532 KB Output is correct
20 Incorrect 77 ms 11728 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 14224 KB Output is correct
2 Correct 111 ms 14248 KB Output is correct
3 Correct 129 ms 14264 KB Output is correct
4 Correct 118 ms 14668 KB Output is correct
5 Correct 117 ms 14728 KB Output is correct
6 Correct 126 ms 14420 KB Output is correct
7 Correct 136 ms 14408 KB Output is correct
8 Correct 114 ms 14476 KB Output is correct
9 Correct 71 ms 12444 KB Output is correct
10 Correct 117 ms 14016 KB Output is correct
11 Correct 115 ms 13796 KB Output is correct
12 Correct 125 ms 14024 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 100 ms 14236 KB Output is correct
3 Correct 114 ms 14304 KB Output is correct
4 Correct 160 ms 14200 KB Output is correct
5 Correct 122 ms 14548 KB Output is correct
6 Correct 118 ms 14360 KB Output is correct
7 Incorrect 121 ms 14600 KB Output isn't correct
8 Halted 0 ms 0 KB -