oj.uz

Submission #663036

# Submission time Handle Problem Language Result Execution time Memory
663036 2022-11-26T14:50:32 Z Ai7081 Strange Device (APIO19_strange_device) C++17
10 / 100
 675 ms 82220 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 = {min(it1->first, it2->first), 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
0 / 10.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 621 ms 67608 KB Output is correct
3 Correct 646 ms 82216 KB Output is correct
4 Correct 675 ms 82116 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 621 ms 67608 KB Output is correct
3 Correct 646 ms 82216 KB Output is correct
4 Correct 675 ms 82116 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 640 ms 82044 KB Output is correct
7 Correct 589 ms 82128 KB Output is correct
8 Correct 618 ms 82220 KB Output is correct
9 Correct 624 ms 82116 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct
2 Correct 621 ms 67608 KB Output is correct
3 Correct 646 ms 82216 KB Output is correct
4 Correct 675 ms 82116 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 62 ms 10168 KB Output is correct
7 Correct 54 ms 10264 KB Output is correct
8 Correct 56 ms 10180 KB Output is correct
9 Correct 63 ms 10280 KB Output is correct
10 Correct 54 ms 10256 KB Output is correct
11 Correct 54 ms 10212 KB Output is correct
12 Correct 56 ms 10252 KB Output is correct
13 Correct 57 ms 10272 KB Output is correct
14 Correct 59 ms 10252 KB Output is correct
15 Incorrect 60 ms 10168 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 57 ms 10188 KB Output is correct
3 Correct 62 ms 10260 KB Output is correct
4 Correct 615 ms 82084 KB Output is correct
5 Correct 57 ms 10248 KB Output is correct
6 Correct 59 ms 10212 KB Output is correct
7 Correct 57 ms 10240 KB Output is correct
8 Correct 56 ms 10168 KB Output is correct
9 Correct 56 ms 10180 KB Output is correct
10 Correct 55 ms 10196 KB Output is correct
11 Correct 57 ms 10240 KB Output is correct
12 Correct 56 ms 10252 KB Output is correct
13 Correct 58 ms 10216 KB Output is correct
14 Incorrect 638 ms 82216 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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