QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#108231	#6334. Passport	ikaurov^#	54	222ms	48504kb	C++17	2.3kb	2023-05-23 22:14:05	2024-05-31 13:42:16

Judging History

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

[2024-05-31 13:42:16]
评测

测评结果：54
用时：222ms
内存：48504kb

查看

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

[2023-05-23 22:14:05]
提交

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 = 2505, INF = 1e9;

queue<pair<int, int>> minset[N];

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  int n;
  cin >> n;
  vector<int> lft(n), rgt(n), mincovered(n, INF);
  vector<vector<int>> segends(n), segstarts(n);
  for (int i = 0; i < n; i++){
    cin >> lft[i] >> rgt[i];
    lft[i]--, rgt[i]--;
    segends[rgt[i]].pb(i);
    segstarts[lft[i]].pb(i);
  }
  int q;
  cin >> q;
  vector<int> queries(q);
  for (auto& i : queries){
    cin >> i;
    i--;
  }
  if (q == 1 && queries[0] == 0){
    int prevrb = -1, rb = rgt[0], ans = 1;
    while (rb < n - 1){
      int newrb = rb;
      for (int i = prevrb + 1; i <= rb; i++){
        newrb = max(newrb, rgt[i]);
      }
      if (newrb == rb){
        cout << -1 << endl;
        return 0;
      }
      prevrb = rb, rb = newrb, ans++;
    }
    cout << ans << endl;
    return 0;
  }
  vector<vector<int>> dp(n, vector<int>(n, INF));
  dp[0][n - 1] = 0;
  for (int l = 0; l < n; l++){
    dp[l][l] = min(dp[l][l], mincovered[l]);
    for (int r = l + 1; r < n; r++){
      if (!minset[r].empty()){
        dp[l][r] = min(dp[l][r], minset[r].front().fi);
        if (minset[r].front().se == l) minset[r].pop();
      }
      dp[l][r] = min({dp[l][r], dp[l][r - 1], mincovered[r]});
    }
    multiset<int> s;
    vector<int> val(n, -1);
    for (int r = n - 1; r >= l; r--){
      if (!s.empty()) dp[l][r] = min(dp[l][r], *s.begin());
      if (val[r] != -1) s.erase(s.find(val[r]));
      for (auto i : segends[r]){
        if (lft[i] < l) continue;
        if (lft[i] == l){
          mincovered[i] = min(mincovered[i], dp[l][r] + 1);
        }
        if (i == r) continue;
        val[i] = dp[l][r] + 1;
        s.insert(val[i]);
      }
      for (auto i : segstarts[l]){
        if (i == l || i > r) continue;
        if (minset[r].empty() || minset[r].back().se < i) minset[r].push({dp[l][r] + 1, i});
      }
    }
  }
  for (auto i : queries) cout << (dp[i][i] == INF? -1 : dp[i][i]) << endl;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 6

Accepted

Test #1:

score: 6

Accepted

time: 1ms

memory: 5244kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 5248kb

input:

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 42ms

memory: 23852kb

input:

output:

result:

ok single line: '3'

Test #4:

score: 0

Accepted

time: 33ms

memory: 24516kb

input:

output:

result:

ok single line: '15219'

Test #5:

score: 0

Accepted

time: 27ms

memory: 29068kb

input:

output:

result:

ok single line: '199999'

Test #6:

score: 0

Accepted

time: 16ms

memory: 17956kb

input:

output:

result:

ok single line: '1'

Test #7:

score: 0

Accepted

time: 13ms

memory: 15904kb

input:

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 1ms

memory: 5280kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 1ms

memory: 5304kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5476kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 1ms

memory: 5312kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5284kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 1ms

memory: 5312kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 3ms

memory: 5700kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 3ms

memory: 5780kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 0ms

memory: 5988kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 3ms

memory: 5612kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 0ms

memory: 6024kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 207ms

memory: 27012kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 155ms

memory: 30572kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 175ms

memory: 30812kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 137ms

memory: 29208kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 88ms

memory: 30828kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 102ms

memory: 31040kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 147ms

memory: 48504kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 112ms

memory: 39256kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 69ms

memory: 30092kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 222ms

memory: 28552kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 152ms

memory: 31332kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 83ms

memory: 30804kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 102ms

memory: 31408kb

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

memory: 33732kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 0

Memory Limit Exceeded

Test #33:

score: 0

Memory Limit Exceeded

input: