oj.uz

Submission #447438

# Submission time Handle Problem Language Result Execution time Memory
447438 2021-07-26T10:31:49 Z Mahdi Strange Device (APIO19_strange_device) C++17
5 / 100
 838 ms 78416 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){
    if(m.empty()){
        m.insert({x, y});
        return;
    }
    auto it=m.upper_bound(x);
    if(it!=m.begin()){
        --it;
        if(it->S>=x){
            if(it->S>=y)
                return;
            x=it->F;
            m.erase(it);
        }
        ++it;
    }
    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 1 ms 204 KB Output is correct
2 Runtime error 7 ms 816 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 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 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 838 ms 78416 KB Output is correct
3 Runtime error 398 ms 33400 KB Execution killed with signal 11
4 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 Runtime error 41 ms 3568 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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