oj.uz

Submission #208165

# Submission time Handle Problem Language Result Execution time Memory
208165 2020-03-10T06:47:18 Z egekabas Strange Device (APIO19_strange_device) C++14
10 / 100
 617 ms 40768 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    ll n, a, b;
    ll mod;
    cin >> n >> a >> b;
    if((b+1)%a == 0)
        mod = b;
    else{
        if(a > (ll(1e18+5))/b+1)
            mod = 1e18+5;
        else
            mod = min(b*a, ll(1e18+5));
    }
    vector<pll> seg;
    for(ll i = 0; i < n; ++i){
        pll tmp;
        cin >> tmp.ff >> tmp.ss;
        if(tmp.ss - tmp.ff + 1 >= mod){
            cout << mod << '\n';
            return 0;
        }
        tmp.ff %= mod;
        tmp.ss %= mod;
        //cout << i << ' ' << tmp.ff << ' ' << tmp.ss << '\n';
        if(tmp.ss >= tmp.ff)
            seg.pb({tmp.ff, tmp.ss});
        else{
            seg.pb({tmp.ff, mod-1});
            seg.pb({0, tmp.ss});
        }
    }
    //for(auto u : seg)
    //    cout << u.ff << ' ' << u.ss << '\n';
    sort(seg.begin(), seg.end());
    vector<pll> v;
    for(auto u : seg){
        //cout << u.ff << ' ' << u.ss << '\n';
        if(!v.empty() && v.back().ss >= u.ff)
            v.back().ss = max(v.back().ss, u.ss);
        else
            v.pb(u);
    }
    ll ans = 0;
    for(auto u : v){
        ans += u.ss-u.ff+1;
        //cout << u.ff << ' ' << u.ss << '\n';
    }
    cout << ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 884 KB Output is correct
3 Correct 10 ms 888 KB Output is correct
4 Incorrect 5 ms 376 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 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 391 ms 17008 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 577 ms 40640 KB Output is correct
3 Incorrect 552 ms 40664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 577 ms 40640 KB Output is correct
3 Incorrect 552 ms 40664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 577 ms 40640 KB Output is correct
3 Incorrect 552 ms 40664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 62 ms 4944 KB Output is correct
3 Correct 59 ms 4968 KB Output is correct
4 Correct 617 ms 40660 KB Output is correct
5 Correct 59 ms 4968 KB Output is correct
6 Correct 62 ms 4980 KB Output is correct
7 Correct 60 ms 4968 KB Output is correct
8 Correct 62 ms 4968 KB Output is correct
9 Correct 59 ms 4972 KB Output is correct
10 Correct 63 ms 5248 KB Output is correct
11 Correct 63 ms 4972 KB Output is correct
12 Correct 55 ms 4968 KB Output is correct
13 Correct 60 ms 4968 KB Output is correct
14 Correct 587 ms 40768 KB Output is correct
15 Incorrect 63 ms 4968 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 884 KB Output is correct
3 Correct 10 ms 888 KB Output is correct
4 Incorrect 5 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -