QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108198#6334. Passportikaurov#0 414ms62984kbC++171.8kb2023-05-23 21:13:062024-05-31 13:41:55

Judging History

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

  • [2024-05-31 13:41:55]
  • 评测
  • 测评结果：0
  • 用时：414ms
  • 内存：62984kb
查看
  • [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:13:06]
  • 提交

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

int val[N][N];
multiset<int> s[N];

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) val[i][j] = -1;
  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] = mincovered[l];
    for (int r = l + 1; r < n; r++){
      dp[l][r] = min({dp[l][r], dp[l][r - 1], mincovered[r]});
    }
    for (int r = n - 1; r >= l; r--){
      if (!s[l].empty()) dp[l][r] = min(dp[l][r], *s[l].begin());
      if (val[l][r] != -1) s[l].erase(s[l].find(val[l][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[l][i] = dp[l][r] + 1;
        s[l].insert(val[l][i]);
      }
    }
    for (auto i : segstarts[l]){
      for (int l1 = l + 1; l1 <= i; l1++){
        s[l1].insert(dp[l][rgt[i]] + 1);
        val[l1][i] = dp[l][rgt[i]] + 1;
      }
    }
  }
  int q;
  cin >> q;
  while (q--){
    int x;
    cin >> x;
    x--;
    cout << (dp[x][x] == INF? -1 : dp[x][x]) << endl;
  }
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 6
Accepted
time: 1ms
memory: 5968kb

input:

2
1 1
1 2
1
1

output:

-1

result:

ok single line: '-1'

Test #2:

score: 6
Accepted
time: 0ms
memory: 3760kb

input:

2
1 2
2 2
1
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Runtime Error

input:

196001
1 408
2 37822
1 1221
1 160899
4 62751
3 21706
2 4118
8 70696
8 4916
3 24286
9 443
8 171744
11 170980
7 3541
12 16428
8 71164
1 186827
11 234
2 23141
4 17143
21 9522
10 24
19 15936
3 15884
17 426
14 3188
17 168317
4 1560
25 35
16 39439
21 122
4 17507
8 97645
11 824
25 59856
30 9265
7 151420
37...

output:

result:

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 16
Accepted
time: 1ms
memory: 5772kb

input:

2
1 1
1 2
1
2

output:

1

result:

ok single line: '1'

Test #9:

score: 16
Accepted
time: 1ms
memory: 3704kb

input:

2
1 2
2 2
1
2

output:

-1

result:

ok single line: '-1'

Test #10:

score: 16
Accepted
time: 0ms
memory: 3712kb

input:

6
1 1
2 2
1 3
3 5
5 6
1 6
1
4

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 3800kb

input:

9
1 1
2 2
3 3
1 4
2 8
5 7
4 9
8 8
9 9
1
6

output:

-1

result:

wrong answer 1st lines differ - expected: '3', found: '-1'

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 24
Accepted
time: 367ms
memory: 60676kb

input:

2337
1 3
2 77
1 1397
2 222
3 62
6 1896
7 10
6 950
9 9
10 16
11 455
9 588
13 16
7 1245
9 1342
8 1727
7 122
11 653
9 1094
2 57
11 81
19 1290
6 1584
16 79
14 215
21 61
27 27
16 1458
16 198
26 180
31 31
11 240
33 36
11 121
34 1542
9 1752
14 456
36 43
36 2244
40 40
4 517
42 662
31 1350
33 162
30 843
28 1...

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Wrong Answer
time: 139ms
memory: 51936kb

input:

2486
1 12
2 8
1 7
3 12
2 11
3 15
1 8
4 11
9 15
3 21
11 13
4 15
9 21
9 19
5 15
8 20
8 25
16 24
11 29
11 23
18 23
14 32
17 24
13 27
15 30
21 34
16 29
20 35
19 32
29 34
20 39
21 43
29 40
28 43
26 44
31 45
28 43
35 38
30 40
37 46
40 43
42 42
42 45
43 54
39 51
40 51
45 54
46 57
39 53
47 53
47 54
41 59
49...

output:

546

result:

wrong answer 1st lines differ - expected: '314', found: '546'

Subtask #4:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 414ms
memory: 62984kb

input:

2419
1 883
1 29
3 41
4 2201
1 808
6 45
7 1456
6 134
6 1372
1 1776
4 441
7 208
5 28
4 604
7 56
9 617
8 2115
15 60
13 456
10 2071
18 23
18 39
5 39
21 35
4 75
25 44
24 640
21 30
4 860
30 31
18 78
32 779
1 927
33 34
19 59
34 181
21 502
23 155
39 39
2 254
30 641
42 50
10 2000
41 2220
18 632
35 48
27 905
...

output:

3
3
3
3
3
3
3
3
3
2
3
3
3
3
3
3
3
4
4
3
4
4
3
4
3
4
4
4
3
5
4
4
3
4
4
4
4
4
-1
3
4
4
3
3
4
4
4
3
4
4
4
3
-1
4
4
4
4
3
-1
4
4
4
4
5
4
4
4
4
4
3
4
4
5
4
3
3
4
4
4
4
4
3
4
3
4
4
-1
-1
4
4
4
3
4
4
3
4
3
4
5
4
4
4
4
4
4
4
4
4
5
5
4
5
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
-1
4
4
3
4
4
4
4
5
4
5
4
4
4
5
-1
4
5
4
4...

result:

wrong answer 49th lines differ - expected: '3', found: '4'

Subtask #5:

score: 0
Runtime Error

Test #33:

score: 0
Runtime Error

input:

196830
1 67357
2 183304
3 23390
4 54
1 145887
3 27807
3 12376
1 1013
3 113274
3 191874
6 23342
9 2113
13 94245
3 141449
10 1727
3 51
17 99028
6 193803
8 7452
6 121537
9 23658
18 611
6 4756
4 5141
8 8547
8 66922
13 7021
9 72
3 53043
16 167381
2 15530
5 192
33 33
9 92655
10 36182
20 19992
36 24454
1 6...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-02 19:01:46 | OpenSource Project