oj.uz

Submission #540604

# Submission time Handle Problem Language Result Execution time Memory
540604 2022-03-21T06:48:08 Z krit3379 Strange Device (APIO19_strange_device) C++17
15 / 100
 455 ms 17192 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 1000005

long long a,b,g,rb,l,r,ll,rr,flag,ans;
vector<pair<long long,long long>> p;

int main(){
    int n,i;
    scanf("%d %lld %lld",&n,&a,&b);
    g=__gcd(a,b+1);
    r=a/g;
    if(1e18/a<b){
        for(i=1;i<=n;i++)scanf("%lld %lld",&l,&r),ans+=r-l+1;
        printf("%lld",ans);
        return 0;
    }
    if(1e18/r>=b)rb=r*b;
    else rb=1e18+5;
    for(i=1;i<=n;i++){
        scanf("%lld %lld",&l,&r);
        if(r-l+1>=rb)flag=true;
        l%=rb;
        r%=rb;
        if(l<=r)p.push_back({l,r});
        else p.push_back({l,rb-1}),p.push_back({0,r});
    }
    if(flag){printf("%lld",rb);return 0;}
    sort(p.begin(),p.end());
    ll=-1;
    rr=-2;
    for(auto [l,r]:p){
        if(l<=rr)rr=r;
        else{
            ans+=rr-ll+1;
            ll=l,rr=r;
        }
    }
    ans+=rr-ll+1;
    printf("%lld",ans);
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %lld %lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:14:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         for(i=1;i<=n;i++)scanf("%lld %lld",&l,&r),ans+=r-l+1;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~
strange_device.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%lld %lld",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 7 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 432 ms 17004 KB Output is correct
3 Correct 422 ms 17192 KB Output is correct
4 Correct 424 ms 17076 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 432 ms 17004 KB Output is correct
3 Correct 422 ms 17192 KB Output is correct
4 Correct 424 ms 17076 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 414 ms 17096 KB Output is correct
7 Correct 413 ms 17096 KB Output is correct
8 Correct 392 ms 17036 KB Output is correct
9 Correct 436 ms 17084 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 432 ms 17004 KB Output is correct
3 Correct 422 ms 17192 KB Output is correct
4 Correct 424 ms 17076 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 45 ms 2676 KB Output is correct
7 Correct 43 ms 2624 KB Output is correct
8 Correct 39 ms 2700 KB Output is correct
9 Correct 41 ms 2732 KB Output is correct
10 Correct 42 ms 2752 KB Output is correct
11 Correct 42 ms 2660 KB Output is correct
12 Correct 38 ms 2732 KB Output is correct
13 Correct 42 ms 2720 KB Output is correct
14 Correct 42 ms 2692 KB Output is correct
15 Incorrect 44 ms 2692 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 44 ms 2700 KB Output is correct
3 Correct 43 ms 2632 KB Output is correct
4 Correct 455 ms 17008 KB Output is correct
5 Correct 43 ms 2624 KB Output is correct
6 Correct 42 ms 2632 KB Output is correct
7 Correct 43 ms 2696 KB Output is correct
8 Correct 44 ms 2632 KB Output is correct
9 Correct 44 ms 2612 KB Output is correct
10 Correct 43 ms 2652 KB Output is correct
11 Correct 44 ms 2672 KB Output is correct
12 Correct 40 ms 2744 KB Output is correct
13 Correct 43 ms 2860 KB Output is correct
14 Incorrect 450 ms 17080 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 7 ms 852 KB Output isn't correct
3 Halted 0 ms 0 KB -