Submission #633518

#	Time	Username	Problem	Language	Result	Execution time	Memory
633518		Son	Strange Device (APIO19_strange_device)	C++14	100 / 100	464 ms	53172 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define se second
#define fi first
#define mp make_pair


int n;
LL A,B;
LL L[1000005], R[1000005];
set < pair < LL , LL > > S;

LL gcd( LL a , LL b ){
    if ( b == 0 ) return a;
    return gcd(b,a%b);
}

LL add( LL l, LL r ){
    LL ans = 0;
    while ( true ){
        auto it = S.lower_bound({l,-1});
        if ( it != S.end() ){
            LL ll = it->se, rr = it->fi;
            if ( rr < l || ll > r ) break;
            if ( ll < l ){
                if ( rr <= r ){
                    S.erase(it);
                    ans += rr - l + 1;
                    S.insert({l-1,ll});
                } else if ( rr > r ){
                    S.erase(it);
                    ans += r - l + 1;
                    S.insert({l-1,ll});
                    S.insert({rr,r+1});
                }
            } else if ( ll >= l ){
                if ( rr <= r ){
                    ans += rr - ll + 1;
                    S.erase(it);
                } else if (rr > r) {
                    S.erase(it);
                    ans += r - ll + 1;
                    S.insert({rr,r+1});
                }
            }
        } else break;
    }

    while ( true ){
        auto it = S.lower_bound({l,-1});
        if ( it != S.begin() ){
            it--;
            LL ll = it->se, rr = it->fi;
            if ( rr < l || ll > r ) break;
            if ( ll < l ){
                if ( rr <= r ){
                    S.erase(it);
                    ans += rr - l + 1;
                    S.insert({l-1,ll});
                } else if ( rr > r ){
                    S.erase(it);
                    ans += r - l + 1;
                    S.insert({l-1,ll});
                    S.insert({rr,r+1});
                }
            } else if ( ll >= l ){
                if ( rr <= r ){
                    ans += rr - ll + 1;
                    S.erase(it);
                } else if (rr > r) {
                    S.erase(it);
                    ans += r - ll + 1;
                    S.insert({rr,r+1});
                }
            }
        } else break;
    }
    return ans;
}

int main(){

    scanf("%d%lld%lld",&n,&A,&B);
    for ( int i = 1; i <= n; i++ ){
        scanf("%lld%lld",&L[i],&R[i]);
    }
    LL g = gcd(A,B+1);
    LL ag = A / g;
    if ( R[n] / ag + ((R[n] % ag) > 0) < B ){
        LL ans = 0;
        for ( int i = 1; i <= n; i++ ){
            ans += R[i] - L[i] + 1;
        }
        printf("%lld\n",ans);
    } else {
        LL ans = 0;
        LL cap = ag * 1LL * B;
        S.clear();
        S.insert({cap-1,0});
        for ( int i = 1; i <= n; i++ ){
            if ( (R[i] - L[i] + 1) / cap > 0 ){
                ans = cap;
                break;
            } else {
                if ( L[i] % cap <= R[i] % cap ){
                    ans += add(L[i]%cap, R[i]%cap);
                } else {
                    ans += add(L[i] % cap, cap - 1) + add(0,R[i] % cap);
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d%lld%lld",&n,&A,&B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%lld%lld",&L[i],&R[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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