oj.uz

Submission #663085

# Submission time Handle Problem Language Result Execution time Memory
663085 2022-11-26T15:33:35 Z Ai7081 Strange Device (APIO19_strange_device) C++17
0 / 100
 391 ms 6504 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
 
const ll inf = 1e18+1;
 
ll n, a, b, l, r;
unsigned long long loop;
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;
    a/=gcd(a,b+1);
    while (a>0) {
        loop += (a%10)*b, a/=10;
        if (loop>=inf) break;
    }
    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;
}

/*
3 3 3
4 4
7 9
17 18
ans: 4

3 5 10
1 20
50 68
89 98
ans: 31

1 1000000000000000 1000000000000000000
100000 1000000
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 6 ms 852 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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