QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39009#3310. Steel Slicing 2_slbAC ✓69ms21208kbC++202.0kb2022-07-08 11:25:592022-07-08 11:26:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-08 11:26:01]
  • 评测
  • 测评结果:AC
  • 用时:69ms
  • 内存:21208kb
  • [2022-07-08 11:25:59]
  • 提交

answer

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;

namespace solve
{
    const int maxn = 2.5e5 + 10;
    typedef pair<int, int> pii;

    int a[maxn], b[maxn];
    int n;

    int is[maxn], stk[maxn], top, lst[maxn];

    void main()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i] >> b[i];
        vector<vector<int>> all(n + 1);
        int tot = 0;
        auto work = [&](int *a)
        {
            top = 0;
            memset(is, 0, sizeof(is)), memset(lst, 0, sizeof(lst));
            vector<int> o(1000100);
            for (int i = 1; i <= n; i++)
                lst[i] = o[a[i]], o[a[i]] = i;
            for (int i = 1; i <= n; i++)
            {
                while (top > 0 && a[i] < a[stk[top]])
                    is[stk[top--]] = 0;
                is[stk[++top] = i] = 1;
                if (lst[i] && is[lst[i]])
                {
                    if (lst[i] < i - 1)
                        all[lst[i]].push_back(i - 1), tot++;
                }
            }
        };
        work(a), work(b);
        int ao = 0;
        for (int i = 1; i < n; i++)
            ao += a[i] != a[i + 1], ao += b[i] != b[i + 1];
        int match = 0;
        priority_queue<int> q;
        for (int i = 1; i < n; i++)
        {
            for (int x : all[i])
                q.push(-x);
            if (a[i] != a[i + 1] && b[i] != b[i + 1])
            {
                tot++;
                while (!q.empty() && -q.top() < i)
                    q.pop();
                if (!q.empty())
                {
                    q.pop();
                    match++;
                }
            }
        }
        cout << ao - tot + match << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve::main();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 11192kb

input:

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

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 4ms
memory: 10368kb

input:

5
23 15
23 17
3 22
15 3
5 1

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 8ms
memory: 10436kb

input:

8
1 2
2 2
2 1
1 1
1 2
2 2
2 2
1 2

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 3ms
memory: 10440kb

input:

2
1 1000000
1000000 1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 3ms
memory: 10532kb

input:

1
1 1

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 4ms
memory: 10536kb

input:

1000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 8ms
memory: 10480kb

input:

1000
2 1
2 1
1 2
1 2
1 2
1 2
2 2
1 1
1 2
1 2
1 1
1 2
2 1
1 1
1 2
2 2
1 1
2 2
1 2
1 2
2 1
2 1
1 2
1 1
1 2
2 2
2 1
2 2
1 2
2 1
1 2
1 2
2 2
1 2
1 2
2 2
2 1
2 1
2 1
1 2
2 1
2 2
1 1
1 2
2 2
2 1
1 1
1 1
2 1
2 2
2 2
1 1
1 1
1 1
1 1
2 1
2 2
1 2
2 1
2 2
1 1
2 2
2 1
2 1
1 1
2 1
2 1
2 1
1 2
1 1
2 1
2 1
2 1
2 2...

output:

505

result:

ok single line: '505'

Test #8:

score: 0
Accepted
time: 3ms
memory: 10560kb

input:

1000
2 2
3 3
3 1
2 1
1 2
1 1
1 3
2 2
1 2
2 1
3 1
1 3
1 1
3 2
2 3
2 1
2 1
1 2
2 1
3 1
3 1
2 1
1 1
2 2
1 2
2 3
3 1
3 3
2 2
3 1
2 1
3 3
3 3
3 2
2 1
1 1
3 1
3 3
2 1
3 1
1 3
2 3
2 1
2 3
1 3
1 3
1 1
1 2
2 2
3 2
2 1
2 2
2 3
2 2
3 1
2 2
1 1
1 3
1 1
3 3
1 3
3 1
2 2
1 3
2 1
1 1
2 3
3 1
2 1
2 1
3 1
2 3
3 2
1 3...

output:

755

result:

ok single line: '755'

Test #9:

score: 0
Accepted
time: 5ms
memory: 10488kb

input:

1000
1 1
3 4
4 1
1 2
2 3
1 3
4 2
1 3
1 1
4 4
1 2
2 3
1 1
2 3
3 1
3 4
4 3
4 2
1 1
3 3
1 4
3 1
3 3
1 2
4 2
3 2
1 4
4 4
3 1
2 1
1 4
1 4
2 3
1 4
1 2
3 2
3 3
4 4
4 1
1 2
2 4
1 1
4 3
3 3
1 3
1 1
3 1
2 1
4 4
1 4
4 4
3 1
1 4
1 4
1 4
3 4
4 4
3 2
3 4
4 3
2 2
3 2
3 3
2 4
1 2
4 1
2 3
2 2
1 1
1 1
1 1
1 3
4 1
3 3...

output:

898

result:

ok single line: '898'

Test #10:

score: 0
Accepted
time: 1ms
memory: 11356kb

input:

1000
2 3
1 1
2 3
1 3
1 3
5 3
2 2
1 2
2 5
2 1
1 4
2 4
3 1
3 3
2 5
1 4
1 3
2 2
3 5
2 5
3 5
4 3
3 5
1 2
5 3
1 5
3 5
3 5
5 1
5 2
2 3
4 4
2 3
1 5
3 5
2 1
5 5
5 3
3 2
3 4
2 1
1 4
3 2
5 5
1 5
3 4
2 2
5 5
5 1
4 2
3 3
2 2
3 4
4 2
3 1
1 2
2 3
1 4
1 2
3 4
5 3
1 3
5 5
2 4
5 2
5 3
1 3
2 5
4 1
4 4
5 1
4 1
3 3
5 4...

output:

937

result:

ok single line: '937'

Test #11:

score: 0
Accepted
time: 3ms
memory: 10576kb

input:

1000
6 3
2 6
4 1
1 3
4 2
4 5
5 3
6 5
6 6
2 6
6 3
4 1
5 5
4 3
4 6
2 6
5 5
1 3
3 1
6 3
6 2
6 5
2 2
1 3
2 6
5 1
6 6
1 1
5 3
5 3
4 3
6 2
3 5
2 2
5 2
2 1
3 4
3 3
6 3
4 5
3 4
1 6
2 1
4 3
4 4
4 5
5 6
4 6
5 2
1 6
6 4
3 1
3 2
1 5
6 4
5 5
3 4
4 3
4 1
5 1
1 3
5 1
5 3
5 2
6 4
5 4
5 6
1 5
4 3
2 2
1 1
6 1
5 2
3 6...

output:

962

result:

ok single line: '962'

Test #12:

score: 0
Accepted
time: 8ms
memory: 10484kb

input:

1000
1 2
7 2
7 2
7 4
2 7
7 6
7 6
4 6
2 7
6 4
5 6
4 5
6 5
2 2
7 7
4 3
5 6
2 6
7 3
1 1
1 1
6 2
1 6
6 5
6 6
4 4
1 4
3 1
1 5
3 3
5 4
6 3
2 4
7 7
7 1
5 4
2 4
1 2
5 7
5 6
4 7
6 5
5 5
5 7
6 7
7 6
2 2
5 1
2 6
6 7
7 2
6 2
4 7
7 5
1 5
7 5
5 4
5 3
6 7
7 6
3 5
6 3
5 5
7 6
5 4
2 4
1 6
4 3
4 5
1 2
1 3
6 1
5 1
1 6...

output:

967

result:

ok single line: '967'

Test #13:

score: 0
Accepted
time: 3ms
memory: 10828kb

input:

1000
6 5
5 7
8 8
5 4
7 5
7 6
1 7
2 3
6 7
7 4
4 8
6 8
2 1
2 8
5 6
1 1
5 7
5 5
1 8
5 2
7 8
5 1
5 2
1 8
3 6
6 1
6 1
2 1
7 1
7 1
2 2
4 1
8 3
4 8
5 2
4 5
2 4
1 1
4 6
8 3
3 7
5 2
4 3
5 7
8 1
3 8
3 6
6 6
5 1
1 8
4 4
3 5
8 1
5 7
6 3
6 2
6 1
2 1
5 6
7 2
4 3
6 5
7 4
8 8
6 7
7 6
7 8
8 3
2 8
8 2
4 1
4 7
5 4
7 6...

output:

978

result:

ok single line: '978'

Test #14:

score: 0
Accepted
time: 4ms
memory: 11104kb

input:

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

output:

984

result:

ok single line: '984'

Test #15:

score: 0
Accepted
time: 4ms
memory: 10536kb

input:

1000
3 10
1 1
4 3
5 9
7 7
4 9
8 1
5 9
1 6
4 1
9 7
2 10
4 2
4 1
6 10
7 9
5 6
9 4
8 4
1 4
5 5
9 10
7 5
1 1
7 5
9 2
1 8
8 3
8 9
6 1
10 1
10 7
1 6
6 9
2 6
3 5
9 8
10 1
2 2
10 6
2 6
6 7
5 5
4 2
1 9
1 4
7 7
10 1
8 1
2 6
9 1
3 4
7 9
7 8
5 1
2 9
5 2
10 4
2 9
2 1
1 2
10 5
5 4
4 4
9 10
10 1
10 10
5 3
1 8
6 8
...

output:

983

result:

ok single line: '983'

Test #16:

score: 0
Accepted
time: 0ms
memory: 10492kb

input:

1000
14 3
1 30
31 32
12 27
22 26
3 17
11 23
20 41
22 11
40 31
25 9
45 26
50 8
48 35
25 50
45 47
24 42
2 8
28 40
33 24
44 6
38 5
49 21
28 27
8 23
40 49
21 28
27 11
8 7
24 34
11 37
21 1
36 17
14 22
4 46
6 22
30 33
46 9
20 33
8 10
29 31
2 12
4 2
46 41
8 6
12 5
38 42
22 39
43 7
46 20
38 31
31 28
29 8
47...

output:

997

result:

ok single line: '997'

Test #17:

score: 0
Accepted
time: 4ms
memory: 10560kb

input:

1000
45 43
56 96
92 7
59 80
93 9
28 53
71 34
5 89
51 12
29 8
28 32
41 74
96 23
59 4
72 6
98 6
4 26
48 79
65 89
53 35
66 35
63 24
100 53
97 22
25 1
82 12
60 44
88 29
95 67
63 7
84 59
58 11
61 78
10 99
21 11
42 38
60 89
24 68
26 13
6 76
85 11
94 72
3 21
42 20
13 64
61 87
98 57
13 21
33 25
78 31
22 6
5...

output:

999

result:

ok single line: '999'

Test #18:

score: 0
Accepted
time: 7ms
memory: 11228kb

input:

1000
641143 722285
386048 792971
998109 741932
230573 320081
676108 661055
127802 140162
43386 591732
741372 392575
650045 53599
977198 595500
554451 809111
89262 957747
559644 661815
306494 841922
12762 763934
347268 388552
873656 405488
311754 673276
818176 189714
364734 788694
359972 410289
89867...

output:

999

result:

ok single line: '999'

Test #19:

score: 0
Accepted
time: 33ms
memory: 17788kb

input:

250000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1...

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 49ms
memory: 20764kb

input:

250000
1 1
1 1
2 1
2 2
2 1
1 2
2 2
1 2
2 1
1 1
2 1
1 1
2 1
2 1
2 2
1 2
1 1
1 1
2 1
1 1
2 2
1 1
2 2
2 2
2 2
2 2
1 2
1 2
1 2
2 1
1 1
1 1
2 1
1 2
2 2
2 1
2 2
2 1
2 1
1 1
2 2
1 1
1 1
1 1
1 2
2 1
2 2
2 2
2 1
2 1
1 2
2 1
2 2
1 2
1 1
2 1
2 2
2 1
1 1
1 2
2 1
1 2
2 2
2 1
1 2
2 2
1 2
2 1
2 1
2 2
2 2
1 1
1 2
1...

output:

124943

result:

ok single line: '124943'

Test #21:

score: 0
Accepted
time: 55ms
memory: 21004kb

input:

250000
2 3
2 3
1 1
2 3
2 1
1 3
2 1
3 2
1 2
2 3
3 3
2 2
3 1
1 2
3 3
3 3
1 1
2 1
1 2
2 1
3 1
3 1
3 3
1 2
1 2
2 1
1 1
2 3
2 1
3 2
3 1
1 2
2 3
3 2
1 1
1 3
3 1
2 2
2 2
1 3
1 3
2 3
1 3
3 2
1 2
2 3
3 2
1 2
1 1
1 3
3 1
2 2
3 3
1 2
2 1
2 3
1 1
1 2
3 2
1 3
2 1
3 3
3 2
3 1
3 1
3 2
3 2
2 1
3 3
1 3
2 3
2 2
3 3
2...

output:

192561

result:

ok single line: '192561'

Test #22:

score: 0
Accepted
time: 43ms
memory: 20600kb

input:

250000
4 1
2 2
3 4
2 1
3 4
3 1
2 3
4 4
2 2
3 1
3 4
3 4
3 1
4 3
4 1
2 4
1 3
2 1
2 2
1 2
3 3
2 2
1 1
4 3
1 4
2 2
4 3
2 4
1 2
3 3
1 4
2 1
2 2
4 4
4 2
3 1
3 4
1 1
4 1
4 3
4 3
4 4
3 3
4 1
2 3
1 1
2 4
2 4
2 2
2 1
1 2
4 1
2 3
3 1
2 2
4 4
2 4
2 3
2 4
1 4
3 2
2 3
1 2
1 4
2 3
4 3
1 4
1 2
4 2
4 2
3 4
2 3
3 2
3...

output:

224139

result:

ok single line: '224139'

Test #23:

score: 0
Accepted
time: 37ms
memory: 21056kb

input:

250000
5 4
2 3
2 2
2 4
3 1
1 3
3 3
2 2
3 3
4 1
5 1
2 1
1 5
4 1
2 5
1 4
5 1
2 3
5 2
1 4
1 2
3 5
5 4
5 4
5 5
3 3
2 5
2 1
3 4
1 3
1 2
3 4
5 4
5 3
5 4
1 3
5 3
4 1
1 1
5 3
1 2
4 2
2 1
3 3
1 5
3 5
1 5
1 5
2 1
1 1
3 2
1 2
5 2
1 4
5 3
1 2
4 2
1 4
4 4
3 4
3 4
3 5
2 3
4 3
1 4
2 3
5 2
1 2
2 5
1 3
3 5
1 3
4 1
3...

output:

236156

result:

ok single line: '236156'

Test #24:

score: 0
Accepted
time: 45ms
memory: 20888kb

input:

250000
6 1
1 4
1 1
6 3
3 4
6 2
3 3
6 6
4 3
2 5
1 1
4 4
5 1
5 3
5 6
1 2
2 1
4 2
2 4
6 5
6 5
3 4
1 5
6 4
1 2
2 3
6 3
5 4
5 5
5 5
2 3
2 2
3 4
6 6
4 2
6 6
6 3
5 6
4 1
4 5
4 1
2 4
5 1
1 3
5 1
2 6
2 5
1 4
3 4
3 3
3 1
2 5
6 4
5 3
5 1
1 1
5 2
2 5
1 3
4 1
4 1
2 5
5 2
4 4
6 1
5 3
4 5
2 6
5 6
1 1
4 6
4 5
5 1
1...

output:

241063

result:

ok single line: '241063'

Test #25:

score: 0
Accepted
time: 45ms
memory: 20588kb

input:

250000
6 4
7 1
2 2
4 1
2 7
1 4
7 5
7 5
1 5
1 3
1 4
6 6
3 4
3 1
2 4
1 5
1 5
5 4
3 6
4 2
5 5
4 3
3 2
1 6
4 6
2 4
1 7
4 7
1 2
6 5
7 6
5 5
6 7
7 4
5 7
7 4
7 5
6 4
3 1
2 7
5 3
1 1
7 4
5 2
6 2
7 3
5 5
3 2
6 6
2 4
2 3
3 3
1 5
1 3
4 3
1 5
4 6
5 6
1 6
3 7
6 5
1 4
7 2
1 7
3 5
5 2
1 4
4 6
4 7
4 5
3 5
6 4
1 5
4...

output:

243757

result:

ok single line: '243757'

Test #26:

score: 0
Accepted
time: 53ms
memory: 19796kb

input:

250000
5 1
5 1
7 6
2 6
8 5
1 7
3 8
8 1
7 4
6 1
6 2
8 5
8 1
7 4
6 2
8 1
7 3
2 4
6 5
3 8
1 6
4 6
4 8
8 1
4 8
1 1
5 8
3 8
5 5
7 7
6 1
2 2
7 2
3 8
4 2
8 4
2 5
2 7
4 6
4 3
1 2
8 1
3 3
2 4
1 6
3 4
6 5
7 5
8 6
7 5
1 3
8 1
2 8
3 8
3 8
3 6
4 1
2 3
8 3
4 2
4 4
1 2
5 7
7 8
7 8
7 3
6 2
4 7
1 1
7 3
2 8
5 3
7 5
7...

output:

245457

result:

ok single line: '245457'

Test #27:

score: 0
Accepted
time: 34ms
memory: 19744kb

input:

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

output:

246382

result:

ok single line: '246382'

Test #28:

score: 0
Accepted
time: 51ms
memory: 20320kb

input:

250000
1 6
6 9
1 3
8 1
10 2
6 6
6 9
6 1
9 9
6 6
1 1
10 7
7 5
8 1
7 3
2 6
4 2
5 2
4 10
4 6
2 4
3 8
8 7
9 1
9 7
5 7
9 3
7 10
6 4
4 8
9 5
3 1
10 1
8 8
4 8
9 2
7 9
8 9
3 8
6 6
7 5
4 10
5 2
6 7
9 5
10 2
1 2
5 7
1 3
7 1
3 10
5 3
5 6
9 4
3 10
10 7
4 7
1 10
4 8
2 5
5 10
2 1
3 9
3 10
10 8
6 6
2 3
9 4
1 9
10 ...

output:

247139

result:

ok single line: '247139'

Test #29:

score: 0
Accepted
time: 35ms
memory: 18820kb

input:

250000
16 1
2 17
9 9
14 4
7 14
16 3
3 4
16 6
2 11
16 19
11 1
12 9
13 19
19 4
6 7
7 20
2 13
2 5
5 17
3 20
1 19
1 13
9 8
20 20
4 6
18 16
11 12
4 14
15 11
6 7
8 18
18 18
13 3
6 7
1 20
5 11
15 11
14 14
11 10
17 7
7 11
12 7
11 1
16 2
13 6
1 5
10 19
17 10
3 11
18 20
9 12
15 4
9 8
11 13
9 2
6 5
5 11
14 5
7...

output:

249366

result:

ok single line: '249366'

Test #30:

score: 0
Accepted
time: 37ms
memory: 18472kb

input:

250000
2 4
30 16
6 8
27 20
25 29
1 6
4 1
15 14
14 30
6 14
5 16
10 11
18 6
25 10
28 4
5 19
7 12
16 9
10 7
15 23
27 14
19 8
30 23
1 4
16 21
27 13
16 17
18 7
23 5
5 18
20 9
28 1
17 23
16 1
8 23
19 2
13 6
12 24
28 30
18 21
30 8
5 22
2 23
17 28
15 30
16 18
22 6
7 18
1 20
18 14
16 29
16 23
22 23
11 27
2 3...

output:

249723

result:

ok single line: '249723'

Test #31:

score: 0
Accepted
time: 49ms
memory: 18128kb

input:

250000
8 39
39 26
15 7
12 29
35 32
25 37
9 10
35 10
18 8
36 17
40 32
3 21
4 14
26 33
35 16
39 15
20 19
3 36
11 5
30 9
34 9
33 20
11 30
10 13
39 40
20 25
10 30
36 11
12 18
37 30
33 12
5 4
26 15
14 18
11 11
14 9
27 25
39 7
14 18
23 36
6 25
33 6
38 12
11 21
6 31
22 15
18 16
33 13
11 12
31 4
12 33
36 14...

output:

249831

result:

ok single line: '249831'

Test #32:

score: 0
Accepted
time: 31ms
memory: 18572kb

input:

250000
40 13
39 14
27 40
46 10
5 44
39 50
34 19
14 43
27 4
18 32
48 11
39 13
22 23
31 15
7 11
30 48
19 32
38 43
33 50
1 36
10 34
37 21
2 21
21 31
16 25
18 24
5 45
48 13
50 35
35 15
42 15
30 5
35 12
34 21
47 22
22 26
30 37
3 22
12 31
4 21
30 23
32 49
36 23
33 26
40 21
41 46
30 33
43 11
32 15
21 29
27...

output:

249889

result:

ok single line: '249889'

Test #33:

score: 0
Accepted
time: 50ms
memory: 17684kb

input:

250000
62 50
56 57
27 47
68 15
41 66
7 24
44 31
11 42
6 59
1 33
53 33
48 70
49 17
59 16
8 60
37 63
9 30
6 74
70 12
2 53
26 14
26 37
20 42
66 73
54 4
59 29
18 25
47 59
1 3
75 65
27 16
4 3
33 66
10 30
43 44
43 32
11 29
69 31
14 14
42 68
3 20
50 10
2 20
73 38
60 11
22 16
64 69
21 12
29 72
49 22
61 63
6...

output:

249962

result:

ok single line: '249962'

Test #34:

score: 0
Accepted
time: 33ms
memory: 18240kb

input:

250000
51 18
14 39
83 50
31 100
63 89
33 3
93 28
10 51
88 77
96 95
9 31
9 47
28 81
19 65
96 91
1 69
35 68
33 9
92 86
60 29
31 5
93 16
21 12
26 93
1 94
89 23
32 67
85 34
41 65
63 4
98 39
77 5
9 25
50 43
20 54
15 66
78 85
84 73
39 81
13 63
12 25
81 55
32 80
67 49
45 9
68 47
65 4
38 21
81 28
57 77
82 9...

output:

249972

result:

ok single line: '249972'

Test #35:

score: 0
Accepted
time: 54ms
memory: 16752kb

input:

250000
154618 123667
38065 78010
171668 237213
172162 238536
155990 209891
243536 119156
97697 113781
40342 37414
202504 153572
245922 31931
32851 179769
127940 171908
196076 168653
36259 69557
197060 179327
69191 234550
131023 87857
2736 42437
110484 98859
144478 40179
68478 63079
13670 31570
22214...

output:

249999

result:

ok single line: '249999'

Test #36:

score: 0
Accepted
time: 61ms
memory: 17428kb

input:

250000
886198 486228
152922 220322
199182 254057
61343 409762
545109 491305
596823 485052
240782 884098
276105 281743
598112 246694
877275 568703
100116 690185
764698 857905
229208 938276
658614 616403
844478 164405
780098 832594
91453 879229
809272 867873
675183 883904
909108 976761
291794 634377
4...

output:

249999

result:

ok single line: '249999'

Test #37:

score: 0
Accepted
time: 28ms
memory: 17444kb

input:

250000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1...

output:

198

result:

ok single line: '198'

Test #38:

score: 0
Accepted
time: 35ms
memory: 17704kb

input:

250000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1...

output:

1998

result:

ok single line: '1998'

Test #39:

score: 0
Accepted
time: 32ms
memory: 18300kb

input:

250000
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
3 3
3 3
3 3
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 5
3 5
4 5
4 5
4 5
4 5
4 5
4 5
4 6
4 6
4 6
4 6
4 6
4 6
4 6
5 6
5 6
5 6
5 6
5 6
5 6
5 6
5 7
5 7
5 7
5...

output:

19998

result:

ok single line: '19998'

Test #40:

score: 0
Accepted
time: 63ms
memory: 19780kb

input:

250000
1 1
1 2
3 2
3 2
3 2
4 3
6 5
7 5
7 5
7 5
10 5
10 6
11 7
11 8
12 8
13 9
14 9
15 9
16 11
18 11
22 12
22 12
23 12
25 12
26 13
27 17
27 17
28 17
28 17
28 17
30 18
30 19
31 19
31 19
33 20
33 20
33 21
35 22
35 23
36 23
37 26
37 27
37 28
38 28
38 29
39 32
41 32
41 34
41 35
42 36
43 36
44 37
44 38
45 ...

output:

183603

result:

ok single line: '183603'

Test #41:

score: 0
Accepted
time: 38ms
memory: 18632kb

input:

250000
2 11
17 16
28 24
36 42
40 42
53 45
58 47
61 55
73 55
82 64
84 66
87 68
101 70
105 76
115 81
118 89
121 98
136 100
144 100
144 103
146 118
178 118
179 135
182 136
191 144
196 168
201 190
206 190
222 191
251 218
260 225
270 231
289 238
290 247
293 249
313 257
323 267
336 274
336 292
346 293
346...

output:

249073

result:

ok single line: '249073'

Test #42:

score: 0
Accepted
time: 69ms
memory: 21208kb

input:

250000
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52 52...

output:

249999

result:

ok single line: '249999'