oj.uz

Submission #447436

# Submission time Handle Problem Language Result Execution time Memory
447436 2021-07-26T10:22:06 Z Mahdi Strange Device (APIO19_strange_device) C++17
15 / 100
 1137 ms 80104 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e6+5;
ll A, B, l[N], r[N], ans;
map<ll, ll>m;
int n;

void add(ll x, ll y){
    auto it=m.upper_bound(x);
    if(it!=m.begin()){
        --it;
        if(it->S>=x){
            if(it->S>=y)
                return;
            it->S=x-1;
        }
        ++it;
    }
    if(it==m.end()){
        m.insert({x, y});
        return;
    }
    while(it!=m.end()){
        if(it->S<=y)
            m.erase(it);
        else{
            if(it->F<=y){
                y=it->S;
                m.erase(it);
            }
            break;
        }
        ++it;
    }
    m.insert({x, y});
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>A>>B;
    for(int i=0;i<n;++i)
        cin>>l[i]>>r[i];
    ll x=__gcd(A, B+1);
    x=A/x;
    ll inf=1e18;
    if(inf/x<B){
        for(int i=0;i<n;++i)
            ans+=r[i]-l[i]+1;
        cout<<ans;
        return 0;
    }
    B*=x;
    for(int i=0;i<n;++i){
        if(l[i]+B-1<=r[i]){
            cout<<B;
            return 0;
        }
        l[i]%=B;
        r[i]%=B;
        if(r[i]>=l[i])
            add(l[i], r[i]);
        else{
            add(l[i], B-1);
            add(0, r[i]);
        }
    }
    auto it=m.begin();
    while(it!=m.end()){
        ans+=it->S-it->F+1;
        ++it;
    }
    cout<<ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 8 ms 1356 KB Output is correct
3 Correct 7 ms 1356 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Runtime error 2 ms 460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Runtime error 2 ms 456 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 826 ms 80104 KB Output is correct
3 Correct 859 ms 80008 KB Output is correct
4 Correct 1137 ms 79928 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 826 ms 80104 KB Output is correct
3 Correct 859 ms 80008 KB Output is correct
4 Correct 1137 ms 79928 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 923 ms 80008 KB Output is correct
7 Correct 953 ms 80016 KB Output is correct
8 Correct 880 ms 80068 KB Output is correct
9 Correct 1049 ms 80068 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 826 ms 80104 KB Output is correct
3 Correct 859 ms 80008 KB Output is correct
4 Correct 1137 ms 79928 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 71 ms 11748 KB Output is correct
7 Correct 72 ms 11828 KB Output is correct
8 Correct 73 ms 11832 KB Output is correct
9 Correct 83 ms 11804 KB Output is correct
10 Correct 76 ms 11736 KB Output is correct
11 Correct 75 ms 11804 KB Output is correct
12 Correct 81 ms 11820 KB Output is correct
13 Correct 80 ms 11756 KB Output is correct
14 Correct 75 ms 11716 KB Output is correct
15 Runtime error 43 ms 7364 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 100 ms 11728 KB Output is correct
3 Correct 79 ms 11844 KB Output is correct
4 Correct 998 ms 80092 KB Output is correct
5 Correct 83 ms 11844 KB Output is correct
6 Correct 93 ms 11852 KB Output is correct
7 Correct 80 ms 11736 KB Output is correct
8 Correct 91 ms 11796 KB Output is correct
9 Correct 79 ms 11836 KB Output is correct
10 Correct 76 ms 11768 KB Output is correct
11 Correct 77 ms 11844 KB Output is correct
12 Correct 93 ms 11812 KB Output is correct
13 Correct 83 ms 11760 KB Output is correct
14 Runtime error 400 ms 33664 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 8 ms 1356 KB Output is correct
3 Correct 7 ms 1356 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Runtime error 2 ms 460 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -