QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#111787	#6334. Passport	Scintilla	100 ✓	912ms	51104kb	C++14	3.1kb	2023-06-08 19:35:35	2023-06-08 19:35:40

Judging History

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

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

[2023-06-08 19:35:40]
评测

测评结果：100
用时：912ms
内存：51104kb

查看

[2023-06-08 19:35:35]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int inf = 0x3f3f3f3f;

const int N = 2e5 + 10;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

void cmax(int &a, int b) { a < b ? a = b : 1; }
void cmin(int &a, int b) { a > b ? a = b : 1; }

vector <int> operator + (vector <int> a, vector <int> b) {
  a.insert(a.end(), b.begin(), b.end());
  return a;
}

int n, L[N], R[N], fl[N], fr[N], f[N];
bool tag[N];
queue <int> q;
priority_queue <pair <int, int>> pq;

// int c[N];
// void build() { fill(c, c + N, inf); }
// void modify(int u, int k) { for (; u < N; u += u & -u) cmin(c[u], k); }
// int query(int u) { int res = inf; for (; u; u -= u & -u) cmin(res, c[u]); return res; }

#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)

vector <int> dat[N << 2];

void build(int u = 1, int l = 1, int r = n) {
  dat[u].clear();
  if (l == r) return tag[l] = false, void();
  build(ls, l, mid), build(rs, mid + 1, r);
}

void ins(int ml, int mr, int k, int u = 1, int l = 1, int r = n) {
  if (ml <= l && r <= mr) {
    dat[u].emplace_back(k);
    return;
  }
  if (ml <= mid) ins(ml, mr, k, ls, l, mid);
  if (mr > mid) ins(ml, mr, k, rs, mid + 1, r);
}

vector <int> query(int p, int u = 1, int l = 1, int r = n) {
  vector <int> res;
  for (auto it : dat[u]) if (!tag[it]) {
    tag[it] = true, res.emplace_back(it);
  }
  dat[u].clear();
  if (l == r) return res;
  if (p <= mid) res = res + query(p, ls, l, mid);
  else res = res + query(p, rs, mid + 1, r);
  return res;
}

#undef ls
#undef rs
#undef mid

int main() {
  n = read();
  rep(i, 1, n) {
    L[i] = read(), R[i] = read();
    fl[i] = fr[i] = inf;
  }
  build();
  rep(i, 1, n) {
    if (L[i] == 1) fl[i] = 1, q.push(i);
    else ins(L[i], R[i], i);
  }
  while (q.size()) {
    int i = q.front(); q.pop();
    auto id = query(i);
    for (int j : id) fl[j] = fl[i] + 1, q.push(j);
  }
  build();
  rep(i, 1, n) {
    if (R[i] == n) fr[i] = 1, q.push(i);
    else ins(L[i], R[i], i);
  }
  while (q.size()) {
    int i = q.front(); q.pop();
    auto id = query(i);
    for (int j : id) fr[j] = fr[i] + 1, q.push(j);
  }
  rep(i, 1, n) f[i] = fl[i] + fr[i] - 1;
  build();
  rep(i, 1, n) {
    pq.push(make_pair(-f[i], i));
    ins(L[i], R[i], i);
  }
  while (pq.size()) {
    int val = -pq.top().first, i = pq.top().second;
    pq.pop();
    if (val != f[i]) continue;
    auto id = query(i);
    for (int j : id) if (f[i] + 1 < f[j]) {
      f[j] = f[i] + 1, pq.push(make_pair(-f[j], j));
    }
  }
  for (int q = read(); q; -- q) {
    int x = read();
    printf("%d\n", f[x] <= n ? f[x] : -1);
  }
  return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 6ms

memory: 25192kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 3ms

memory: 24168kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 868ms

memory: 48900kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 409ms

memory: 38304kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 491ms

memory: 38272kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 214ms

memory: 30976kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 141ms

memory: 35080kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 5ms

memory: 23996kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 5ms

memory: 24560kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 1ms

memory: 24324kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 3ms

memory: 24096kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 5ms

memory: 23856kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 2ms

memory: 24172kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 0ms

memory: 22944kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 1ms

memory: 23228kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 1ms

memory: 23064kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 10ms

memory: 23916kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 3ms

memory: 23932kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 5ms

memory: 25412kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 4ms

memory: 23984kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 7ms

memory: 26128kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 4ms

memory: 23600kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 6ms

memory: 23640kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 11ms

memory: 24948kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 3ms

memory: 22956kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 2ms

memory: 24872kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 3ms

memory: 22912kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 9ms

memory: 24068kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 4ms

memory: 23664kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 8ms

memory: 22680kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 7ms

memory: 24380kb

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

memory: 24216kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 46

Accepted

Test #33:

score: 46

Accepted

time: 912ms

memory: 51104kb

input:

output:

result:

ok 196830 lines

Test #34:

score: 0

Accepted

time: 463ms

memory: 38392kb

input:

output:

result:

ok 199765 lines

Test #35:

score: 0

Accepted

time: 523ms

memory: 48084kb

input:

output:

result:

ok 199851 lines

Test #36:

score: 0

Accepted

time: 491ms

memory: 48648kb

input:

output:

result:

ok 199992 lines

Test #37:

score: 0

Accepted

time: 496ms

memory: 38232kb

input:

output:

result:

ok 200000 lines

Test #38:

score: 0

Accepted

time: 524ms

memory: 39416kb

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

memory: 28332kb

input:

output:

result:

ok 74422 lines

Test #40:

score: 0

Accepted

time: 457ms

memory: 40960kb

input:

output:

result:

ok 198765 lines

Test #41:

score: 0

Accepted

time: 504ms

memory: 41320kb

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