QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#108224	#6334. Passport	ikaurov^#	48	226ms	48196kb	C++17	1.9kb	2023-05-23 21:53:30	2024-05-31 13:42:07

Judging History

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

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

测评结果：48
用时：226ms
内存：48196kb

查看

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

[2023-05-23 21:53: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 = 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);
  }
  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});
      }
    }
  }
  int q;
  cin >> q;
  while (q--){
    int x;
    cin >> x;
    x--;
    cout << (dp[x][x] == INF? -1 : dp[x][x]) << endl;
  }
}

源文件, 语言: C++17

详细

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 6

Accepted

time: 1ms

memory: 5508kb

input:

output:

-1

result:

ok single line: '-1'

Test #2:

score: 0

Accepted

time: 1ms

memory: 5212kb

input:

output:

result:

ok single line: '1'

Test #3:

score: -6

Time Limit Exceeded

input:

output:

result:

Subtask #2:

score: 16

Accepted

Test #8:

score: 16

Accepted

time: 1ms

memory: 5288kb

input:

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 2ms

memory: 5288kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5284kb

input:

output:

result:

ok single line: '3'

Test #11:

score: 0

Accepted

time: 1ms

memory: 5228kb

input:

output:

result:

ok single line: '3'

Test #12:

score: 0

Accepted

time: 0ms

memory: 5516kb

input:

output:

result:

ok single line: '3'

Test #13:

score: 0

Accepted

time: 1ms

memory: 5480kb

input:

output:

result:

ok single line: '2'

Test #14:

score: 0

Accepted

time: 4ms

memory: 5640kb

input:

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 3ms

memory: 5720kb

input:

output:

result:

ok single line: '49'

Test #16:

score: 0

Accepted

time: 4ms

memory: 5672kb

input:

output:

result:

ok single line: '10'

Test #17:

score: 0

Accepted

time: 3ms

memory: 5536kb

input:

output:

result:

ok single line: '7'

Test #18:

score: 0

Accepted

time: 3ms

memory: 5740kb

input:

output:

result:

ok single line: '298'

Subtask #3:

score: 24

Accepted

Test #19:

score: 24

Accepted

time: 215ms

memory: 27116kb

input:

output:

result:

ok single line: '4'

Test #20:

score: 0

Accepted

time: 160ms

memory: 30644kb

input:

output:

result:

ok single line: '314'

Test #21:

score: 0

Accepted

time: 184ms

memory: 30916kb

input:

output:

result:

ok single line: '60'

Test #22:

score: 0

Accepted

time: 143ms

memory: 29184kb

input:

output:

result:

ok single line: '20'

Test #23:

score: 0

Accepted

time: 86ms

memory: 30840kb

input:

output:

result:

ok single line: '2498'

Test #24:

score: 0

Accepted

time: 102ms

memory: 31024kb

input:

output:

result:

ok single line: '2498'

Test #25:

score: 0

Accepted

time: 154ms

memory: 48196kb

input:

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 118ms

memory: 39280kb

input:

output:

result:

ok single line: '3'

Test #27:

score: 0

Accepted

time: 62ms

memory: 30040kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 8

Accepted

Test #28:

score: 8

Accepted

time: 226ms

memory: 28516kb

input:

output:

result:

ok 2419 lines

Test #29:

score: 0

Accepted

time: 160ms

memory: 31232kb

input:

output:

result:

ok 2500 lines

Test #30:

score: 0

Accepted

time: 88ms

memory: 30768kb

input:

output:

result:

ok 2500 lines

Test #31:

score: 0

Accepted

time: 108ms

memory: 31540kb

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

memory: 33812kb

input:

output:

result:

ok 2422 lines

Subtask #5:

score: 0

Memory Limit Exceeded

Test #33:

score: 0

Memory Limit Exceeded

input: