Submission #447439

#	Time	Username	Problem	Language	Result	Execution time	Memory
447439		Mahdi	Strange Device (APIO19_strange_device)	C++17	15 / 100	2333 ms	78720 KiB

strange_device

#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;
    }
    it=m.upper_bound(x);
    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
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30