QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#108357	#6334. Passport	ikaurov	100 ✓	609ms	99344kb	C++17	2.3kb	2023-05-24 19:12:30	2023-05-24 19:12:32

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-24 19:12:32]
评测

测评结果：100
用时：609ms
内存：99344kb

查看

[2023-05-24 19:12:30]
提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int N = 2e5 + 20;

vector<pair<int, int>> g[4 * N];
int rep[N];

void build(int v, int tl, int tr){
  if (tl == tr){
    rep[tl] = v;
    return;
  }
  int tm = (tl + tr) / 2;
  g[2 * v + 1].pb({v, 0});
  g[2 * v + 2].pb({v, 0});
  build(2 * v + 1, tl, tm);
  build(2 * v + 2, tm + 1, tr);
}

void decompose(int v, int tl, int tr, int l, int r, int u){
  if (l > r) return;
  if (tl == l && tr == r){
    g[v].pb({u, 1});
    return;
  }
  int tm = (tl + tr) / 2;
  decompose(2 * v + 1, tl, tm, l, min(r, tm), u);
  decompose(2 * v + 2, tm + 1, tr, max(l, tm + 1), r, u);
}

vector<int> dijkstra(vector<int> dist){
  vector<pair<int, int>> q;
  for (int i = 0; i < sz(dist); i++){
    q.pb({dist[i], i});
  }
  sort(all(q));
  reverse(all(q));
  vector<pair<int, int>> nextdist;
  while (!q.empty() || !nextdist.empty()){
    if (!nextdist.empty() && (q.empty() || q.back().fi >= nextdist[0].fi)){
      q.insert(q.end(), nextdist.begin(), nextdist.end());
      nextdist.clear();
    }
    auto [d, v] = q.back();
    q.pop_back();
    if (d != dist[v]) continue;
    for (auto [u, w] : g[v]){
      if (d + w < dist[u]){
        dist[u] = d + w;
        if (dist[u] == d) q.pb({dist[u], u});
        else nextdist.pb({dist[u], u});
      }
    }
  }
  return dist;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  int n;
  cin >> n;
  build(0, 0, n - 1);
  vector<int> l(n), r(n);
  for (int i = 0; i < n; i++){
    cin >> l[i] >> r[i];
    l[i]--, r[i]--;
    decompose(0, 0, n - 1, l[i], r[i], rep[i]);
  }
  vector<int> reachstart(4 * N, N), reachend(4 * N, N);
  reachstart[rep[0]] = 0, reachend[rep[n - 1]] = 0;
  reachstart = dijkstra(reachstart), reachend = dijkstra(reachend);
  vector<int> dist(4 * N, N);
  for (int i = 0; i < n; i++) dist[rep[i]] = min(N, reachstart[rep[i]] + reachend[rep[i]] - (i > 0 && i < n - 1));
  dist = dijkstra(dist);
  int q;
  cin >> q;
  while (q--){
    int x;
    cin >> x;
    x--;
    cout << (dist[rep[x]] == N? -1 : dist[rep[x]]) << endl;
  }
}

源文件, 语言: C++17

详细

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 93ms

memory: 48732kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 88ms

memory: 48568kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 588ms

memory: 91960kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 265ms

memory: 71832kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 227ms

memory: 66508kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 182ms

memory: 64580kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 198ms

memory: 71892kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 88ms

memory: 48656kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 84ms

memory: 48568kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 86ms

memory: 48588kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 89ms

memory: 48596kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 90ms

memory: 48732kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 97ms

memory: 48588kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 80ms

memory: 48616kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 79ms

memory: 48580kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 101ms

memory: 48628kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 87ms

memory: 48628kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 93ms

memory: 48712kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 83ms

memory: 48980kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 80ms

memory: 48956kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 92ms

memory: 49132kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 72ms

memory: 49140kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 97ms

memory: 48964kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 99ms

memory: 49008kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 83ms

memory: 48804kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 80ms

memory: 48908kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 82ms

memory: 49064kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 82ms

memory: 49036kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 95ms

memory: 48900kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 100ms

memory: 48876kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 92ms

memory: 48872kb

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: 97ms

memory: 48904kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 609ms

memory: 92420kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 303ms

memory: 71896kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 396ms

memory: 99020kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 391ms

memory: 99344kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 237ms

memory: 66504kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 284ms

memory: 73972kb

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: 180ms

memory: 57168kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 324ms

memory: 74836kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 407ms

memory: 82712kb

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