Submission #798651

#	Time	Username	Problem	Language	Result	Execution time	Memory
798651		gg123_pe	Strange Device (APIO19_strange_device)	C++14	20 / 100	1218 ms	115744 KiB

strange_device

#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e6 + 5; 
const ll inf = 1e18 + 5; 

int n; 
ll l[N], r[N]; 
ll A, B, S; 

void subtask_1(){
    set <pair<ll,ll>> s;

    f(i,1,n+1){
        for(ll j = l[i]; j <= r[i]; j++){
            ll a, b; 
            a = (j + j/B) % A; 
            b = j % B; 
            s.insert({a, b}); 
        }
    }
    cout << s.size() << "\n"; 
}
void subtask_2(){
    ll X = A / __gcd(A, B+1);  
    ll period = X * B;  
    cout << min(r[1] - l[1] + 1, period) << "\n"; 
}
void subtask_4(){
    if(A%2 == 0) A /= 2; 

    set <pair<ll,ll>> s; 

    f(i,1,n+1){
        ll len = r[i] - l[i] + 1;  
        if(len >= A){
            cout << A << "\n"; 
            return; 
        }
        ll x = l[i] % A;
        if(len > A-x){
            s.insert({x, A-1}); 
            s.insert({0, r[i]%A}); 
        }   
        else{
            s.insert({x, r[i]%A}); 
        }
    }
    ll ans = 0, l, r;
    auto it = s.begin(); 
    l = it->first, r = it->second; 
    for(auto p: s){
        if(p == *it) continue; 
        ll x = p.first, y = p.second; 

        if(x <= r){
            r = max(r, y); 
        }
        else if(x == r+1){
            r = y; 
        }
        else{
            ans += r - l + 1; 
            l = x, r = y; 
        }
    }
    ans += r - l + 1; 
    cout << ans << "\n"; 
}
int main(){
    cin >> n >> A >> B; 

    f(i,1,n+1){
        cin >> l[i] >> r[i]; 
        S += r[i] - l[i] + 1; 
    }

    if(S <= N){
        subtask_1(); 
        return 0; 
    }
    if(n == 1){
        subtask_2(); 
        return 0; 
    }
    if(B == 1){
        subtask_4(); 
        return 0; 
    }
    return 0; 
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30