Submission #249057

#	Time	Username	Problem	Language	Result	Execution time	Memory
249057		sealnot123	Strange Device (APIO19_strange_device)	C++14	100 / 100	549 ms	504 KiB

strange_device

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const int N = 1000005;
int n;
LL A, B;
set<PLL> keep;
set<PLL>::iterator it, it2;
void solve(){
    scanf("%d %lld %lld",&n,&A,&B);
    LL loop = A/__gcd(A,B+1);
    if(loop > 1e18/B){
        loop = 1e18+2;
    }else loop *= B;
    //printf("loop is %lld\n",loop);
    int ch = 0;
    LL ans = 0;
    auto find = [&](LL a){
        return keep.lower_bound(PLL(a,0));
    };
    auto add = [&](LL l, LL r){
        //printf("adding (%lld, %lld)\n",l,r);
        it = find(l+1);
        if(it != keep.begin()) --it;
        for(; it != keep.end();){
            PLL e = *it;
            it2 = it;
            ++it;
            if(e.x > r+1) break;
            if(e.y < l-1) continue;
            l = min(l, e.x); r = max(r, e.y);
            keep.erase(it2);
        }
        keep.insert(PLL(l,r));
    };
    FOR(i, 1, n){
        LL l, r;
        scanf("%lld %lld",&l,&r);
        if(r-l+1 >= loop){
            ch = 1; ans = loop;
        }
        // there is a function called 'prev'
        l %= loop;
        r %= loop;
        if(l > r) add(0,r), add(l,loop-1);
        else add(l,r);
        //printf("keep : ");
        //for(PLL e : keep) printf("[%lld, %lld] ",e.x,e.y);
        //puts("");
    }
    if(ch){ printf("%lld",ans); return ; }
    for(PLL e : keep) ans += e.y-e.x+1;
    printf("%lld",ans);
}

int main(){
    solve();
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld %lld",&n,&A,&B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• 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