oj.uz

Submission #403481

# Submission time Handle Problem Language Result Execution time Memory
403481 2021-05-13T08:32:44 Z Hazem Strange Device (APIO19_strange_device) C++14
15 / 100
 570 ms 49744 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 1e6+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 2e18;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

pair<LL,LL>p[N];
vector<pair<LL,LL>>vec;

LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}

int main(){

    //freopen("out.txt","w",stdout);

    LL n,a,b,Len;
    scanf("%lld%lld%lld",&n,&a,&b);

    // for(int i=0;i<=n;i++)
    //     printf("%d %d\n",(i+i/b)%a,i%b);

    LL g = gcd(a,b+1);
    a /= g;

    if(log(a)+log(b+1)>=log(LLONG_MAX))    
        Len = LINF;
    else 
        Len = a*(b+1)-a;

    bool q = 0;
    for(int i=1;i<=n;i++){

        scanf("%lld%lld",&p[i].F,&p[i].S);
        q |= p[i].S-p[i].F+1>=Len;

        p[i].F %= Len;p[i].S %= Len;

        if(p[i].S>=p[i].F)
            vec.push_back({p[i].F,p[i].S});
        else 
            vec.push_back({p[i].F,Len-1}),vec.push_back({0,p[i].S});
    }

    sort(vec.begin(),vec.end());
    
    LL l = 0,r = -1,ans = 0;
    vec.push_back({LINF,LINF});

    for(int i=0;i<vec.size();i++){
        
        if(vec[i].F>r)
            ans += r-l+1,l = vec[i].F,r = vec[i].S;
        else 
            r = vec[i].S;
    }

    printf("%lld\n",q?Len:ans);
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
strange_device.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%lld%lld%lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%lld%lld",&p[i].F,&p[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 6 ms 844 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 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 204 KB Output is correct
2 Correct 509 ms 31748 KB Output is correct
3 Correct 506 ms 31888 KB Output is correct
4 Correct 503 ms 49580 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 31748 KB Output is correct
3 Correct 506 ms 31888 KB Output is correct
4 Correct 503 ms 49580 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 512 ms 49744 KB Output is correct
7 Correct 528 ms 49720 KB Output is correct
8 Correct 513 ms 49692 KB Output is correct
9 Correct 545 ms 49524 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 31748 KB Output is correct
3 Correct 506 ms 31888 KB Output is correct
4 Correct 503 ms 49580 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 51 ms 7260 KB Output is correct
7 Correct 53 ms 7212 KB Output is correct
8 Correct 52 ms 7268 KB Output is correct
9 Correct 51 ms 7200 KB Output is correct
10 Correct 51 ms 7240 KB Output is correct
11 Correct 57 ms 7248 KB Output is correct
12 Correct 52 ms 7152 KB Output is correct
13 Correct 53 ms 7156 KB Output is correct
14 Correct 53 ms 7232 KB Output is correct
15 Incorrect 56 ms 7236 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 204 KB Output is correct
2 Correct 54 ms 4976 KB Output is correct
3 Correct 54 ms 5040 KB Output is correct
4 Correct 570 ms 31740 KB Output is correct
5 Correct 54 ms 4784 KB Output is correct
6 Correct 55 ms 4808 KB Output is correct
7 Correct 55 ms 4828 KB Output is correct
8 Correct 55 ms 4708 KB Output is correct
9 Correct 54 ms 4784 KB Output is correct
10 Correct 56 ms 4788 KB Output is correct
11 Correct 55 ms 4768 KB Output is correct
12 Correct 50 ms 4992 KB Output is correct
13 Correct 55 ms 4784 KB Output is correct
14 Incorrect 541 ms 31736 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 204 KB Output is correct
2 Incorrect 6 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -