oj.uz

Submission #208163

# Submission time Handle Problem Language Result Execution time Memory
208163 2020-03-10T06:44:17 Z egekabas Strange Device (APIO19_strange_device) C++14
5 / 100
 622 ms 47936 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
        mod = min(b*a, ll(1e18));
    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 888 KB Output is correct
3 Correct 13 ms 892 KB Output is correct
4 Incorrect 5 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 5 ms 376 KB Output isn't 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 6 ms 376 KB Output is correct
5 Correct 383 ms 16980 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 558 ms 40616 KB Output is correct
3 Incorrect 551 ms 47936 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 558 ms 40616 KB Output is correct
3 Incorrect 551 ms 47936 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 558 ms 40616 KB Output is correct
3 Incorrect 551 ms 47936 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 64 ms 5096 KB Output is correct
3 Correct 60 ms 4968 KB Output is correct
4 Correct 622 ms 40768 KB Output is correct
5 Correct 62 ms 4968 KB Output is correct
6 Correct 59 ms 4968 KB Output is correct
7 Correct 61 ms 4968 KB Output is correct
8 Correct 64 ms 4964 KB Output is correct
9 Correct 59 ms 4968 KB Output is correct
10 Correct 60 ms 4972 KB Output is correct
11 Correct 64 ms 4968 KB Output is correct
12 Correct 58 ms 4968 KB Output is correct
13 Correct 59 ms 4968 KB Output is correct
14 Correct 604 ms 40760 KB Output is correct
15 Incorrect 61 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 888 KB Output is correct
3 Correct 13 ms 892 KB Output is correct
4 Incorrect 5 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -