oj.uz

Submission #663038

# Submission time Handle Problem Language Result Execution time Memory
663038 2022-11-26T14:52:57 Z Ai7081 Strange Device (APIO19_strange_device) C++17
65 / 100
 649 ms 82100 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

const int N = 1e6 + 5;

ll n, a, b, loop, l, r;
set<pii> s;

ll gcd(ll c1, ll c2) {
    if (!(max(c1,c2)%min(c1,c2))) return min(c1, c2);
    return gcd(min(c1,c2), max(c1,c2)%min(c1,c2));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    loop = a*b/gcd(a,b+1);
    while (n--) {
        cin >> l >> r, l%=loop, r%=loop;
        if (l>r) s.insert({0,r}), s.insert({l,loop-1});
        else s.insert({l,r});
    }
    auto it2=s.begin(), it1=it2++;
    while (it2!=s.end()) {
        if (it1->second >= it2->first) {
            pii in = {it1->first, max(it1->second, it2->second)};
            it1=s.erase(it1), it1=s.erase(it1);
            it2=s.insert(in).first;
        }
        it1=it2++;
    }
    ll out=0;
    for (auto [x,y]:s) out += y-x+1;
    cout << out;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1296 KB Output is correct
17 Correct 59 ms 10160 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 278 ms 25476 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 549 ms 63004 KB Output is correct
3 Correct 585 ms 62892 KB Output is correct
4 Correct 598 ms 62996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 549 ms 63004 KB Output is correct
3 Correct 585 ms 62892 KB Output is correct
4 Correct 598 ms 62996 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 567 ms 62976 KB Output is correct
7 Correct 593 ms 62868 KB Output is correct
8 Correct 567 ms 62924 KB Output is correct
9 Correct 593 ms 62800 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 549 ms 63004 KB Output is correct
3 Correct 585 ms 62892 KB Output is correct
4 Correct 598 ms 62996 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 51 ms 6488 KB Output is correct
7 Correct 51 ms 6536 KB Output is correct
8 Correct 54 ms 6476 KB Output is correct
9 Correct 53 ms 6528 KB Output is correct
10 Correct 48 ms 6468 KB Output is correct
11 Correct 53 ms 6480 KB Output is correct
12 Correct 52 ms 6548 KB Output is correct
13 Correct 54 ms 6548 KB Output is correct
14 Correct 51 ms 6560 KB Output is correct
15 Correct 60 ms 6476 KB Output is correct
16 Correct 66 ms 10176 KB Output is correct
17 Correct 59 ms 10264 KB Output is correct
18 Correct 636 ms 82000 KB Output is correct
19 Correct 644 ms 82100 KB Output is correct
20 Correct 649 ms 82092 KB Output is correct
21 Correct 57 ms 10232 KB Output is correct
22 Correct 53 ms 10188 KB Output is correct
23 Correct 115 ms 12832 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 74 ms 6472 KB Output is correct
3 Correct 58 ms 6476 KB Output is correct
4 Correct 579 ms 63004 KB Output is correct
5 Correct 56 ms 6476 KB Output is correct
6 Correct 56 ms 6444 KB Output is correct
7 Correct 56 ms 6476 KB Output is correct
8 Correct 53 ms 6524 KB Output is correct
9 Correct 54 ms 6452 KB Output is correct
10 Correct 52 ms 6504 KB Output is correct
11 Correct 54 ms 6508 KB Output is correct
12 Correct 73 ms 6508 KB Output is correct
13 Correct 56 ms 6452 KB Output is correct
14 Correct 610 ms 62996 KB Output is correct
15 Correct 57 ms 10264 KB Output is correct
16 Correct 599 ms 81960 KB Output is correct
17 Correct 584 ms 82076 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1296 KB Output is correct
17 Correct 59 ms 10160 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -