QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#150837	#6334. Passport	JCY_	100 ✓	391ms	68824kb	C++17	2.3kb	2023-08-26 13:51:23	2023-08-26 13:51:26

Judging History

你现在查看的是最新测评结果

[2023-08-26 13:51:26]
评测

测评结果：100
用时：391ms
内存：68824kb

查看

[2023-08-26 13:51:23]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
constexpr int MAXN = 2e5 + 10, INF = 0x3f3f3f3f;
int n, ls[MAXN * 2], rs[MAXN * 2], tot, dis1[MAXN * 2], dis2[MAXN * 2];
vector<pair<int, int>> g[MAXN * 2];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int build(int l, int r) {
  if (l == r) return l;
  int u = ++tot, mid = (l + r) >> 1;
  ls[u] = build(l, mid);
  rs[u] = build(mid + 1, r);
  g[ls[u]].emplace_back(u, 0);
  g[rs[u]].emplace_back(u, 0);
  return u;
}
void add_edge(int u, int l, int r, int ql, int qr, int x) {
  if (ql <= l && r <= qr) {
    g[u].emplace_back(x, 1);
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) add_edge(ls[u], l, mid, ql, qr, x);
  if (qr > mid) add_edge(rs[u], mid + 1, r, ql, qr, x);
}
void dijkstra(int dis[]) {
  for (int i = 0; i <= tot; ++i)
    if (dis[i] != INF) pq.emplace(dis[i], i);
  while (!pq.empty()) {
    int d, u;
    tie(d, u) = pq.top();
    pq.pop();
    if (d > dis[u]) continue;
    for (auto &e : g[u]) {
      int v, w;
      tie(v, w) = e;
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        pq.emplace(dis[v], v);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  tot = n + 1;
  int rt = build(1, n);
  for (int i = 1, l, r; i <= n; ++i) {
    cin >> l >> r;
    if (l == 1) g[0].emplace_back(i, 1);
    if (r == n) g[n + 1].emplace_back(i, 1);
    add_edge(rt, 1, n, l, r, i);
  }
  fill(dis1 + 1, dis1 + tot + 1, INF);
  dijkstra(dis1);
  fill(dis2, dis2 + tot + 1, INF);
  dis2[n + 1] = 0;
  dijkstra(dis2);
  for (int i = 0; i <= tot; ++i) {
    dis2[i] = min(dis2[i] + dis1[i], INF);
    if (!i || i > n) dis2[i] = INF;
  }
  dijkstra(dis2);
  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    cout << (dis2[x] == INF ? -1 : dis2[x] - 1) << "\n";
  }
  return 0;
}
// g++ passport.cpp -o passport -Wall -Wextra -Wshadow -O2 -std=c++14 -fsanitize=address,undefined

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 0ms

memory: 18772kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 18040kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 345ms

memory: 61616kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 182ms

memory: 41636kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 83ms

memory: 36124kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 125ms

memory: 38296kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 55ms

memory: 42112kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 4ms

memory: 17388kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 0ms

memory: 18800kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 3ms

memory: 17636kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 0ms

memory: 18092kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 3ms

memory: 18752kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 1ms

memory: 17556kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 3ms

memory: 18304kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 2ms

memory: 18596kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 0ms

memory: 17560kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 3ms

memory: 17548kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 2ms

memory: 18416kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 5ms

memory: 17844kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 1ms

memory: 17960kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 5ms

memory: 18000kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 5ms

memory: 18816kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 4ms

memory: 17524kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 4ms

memory: 18904kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 1ms

memory: 18336kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 5ms

memory: 17584kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 2ms

memory: 17880kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 6ms

memory: 18084kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 5ms

memory: 18492kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 3ms

memory: 17708kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 0ms

memory: 18208kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 2500 lines

Test #32:

score: 0

Accepted

time: 2ms

memory: 18320kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 391ms

memory: 64532kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 198ms

memory: 41556kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 249ms

memory: 68824kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 251ms

memory: 68204kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 115ms

memory: 35656kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 123ms

memory: 43048kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #39:

score: 0

Accepted

time: 77ms

memory: 27384kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 199ms

memory: 45484kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 179ms

memory: 51220kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 199636 lines

Extra Test:

score: 0

Extra Test Passed