oj.uz

Submission #722943

# Submission time Handle Problem Language Result Execution time Memory
722943 2023-04-13T06:07:01 Z nicky4321 Strange Device (APIO19_strange_device) C++17
10 / 100
 799 ms 115656 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define vi vector<int>
#define vl vector<ll>
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
ll l[MAX], r[MAX];

void solve(){
    ll n, a, b;
    cin >> n >> a >> b;
    for(int i = 1;i <= n;i++){
        cin >> l[i] >> r[i];
    }
    ll mod;
    if(a == b + 1)
        mod = b;
    else{
        if((__int128_t)a * b >= 1000000000000000000){
            ll ans = 0;
            for(int i = 1;i <= n;i++)
                ans += r[i] - l[i] + 1;
            cout << ans << '\n';
            return;
        }
        mod = a * b;
    }
    map<ll, int> mp;
    for(int i = 1;i <= n;i++){
        if(r[i] - l[i] + 1 >= mod){
            cout << mod << '\n';
            return;
        }
        l[i] %= mod;
        r[i] %= mod;
        if(l[i] <= r[i]){
            mp[l[i]]++;
            mp[r[i] + 1]--;
        }else{
            mp[0]++;
            mp[r[i] + 1]--;
            mp[l[i]]++;
            mp[mod]--;
        }
    }
    ll lt = 0, now = 0, ans = 0;
    for(auto i : mp){
        if(now > 0)
            ans += i.F - lt;
        now += i.S;
        lt = i.F;
    }
    cout << ans << '\n';
}

int main(){
    IOS
    solve();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 1492 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 305 ms 41072 KB Output is correct

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 84 ms 11768 KB Output is correct
3 Correct 67 ms 11836 KB Output is correct
4 Correct 769 ms 115592 KB Output is correct
5 Correct 66 ms 12040 KB Output is correct
6 Correct 75 ms 11916 KB Output is correct
7 Correct 101 ms 11816 KB Output is correct
8 Correct 64 ms 11852 KB Output is correct
9 Correct 64 ms 11844 KB Output is correct
10 Correct 60 ms 11808 KB Output is correct
11 Correct 73 ms 11828 KB Output is correct
12 Correct 60 ms 11792 KB Output is correct
13 Correct 66 ms 11852 KB Output is correct
14 Correct 753 ms 115656 KB Output is correct
15 Incorrect 72 ms 11852 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 1492 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -