oj.uz

Submission #403478

# Submission time Handle Problem Language Result Execution time Memory
403478 2021-05-13T08:31:16 Z Hazem Strange Device (APIO19_strange_device) C++14
10 / 100
 5000 ms 524292 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;
    set<LL>st;
    LL ans = 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].F<=p[i].S)
             //ans += p[i].S-p[i].F+1;
         for(int j=p[i].F;j<=p[i].S;j++)
             st.insert(j);
        
        else {
            
            //ans += Len-p[i].F;
             for(int j=p[i].F;j<=Len-1;j++)
                 st.insert(j);
            
             for(int j=0;j<=p[i].S;j++)
                 st.insert(j);
            //ans += p[i].S+1;
        }

        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:st.size());
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:42:8: warning: unused variable 'ans' [-Wunused-variable]
   42 |     LL ans = 0;
      |        ^~~
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:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld%lld",&p[i].F,&p[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 44 ms 9600 KB Output is correct
3 Correct 69 ms 13768 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 972 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 32 ms 5352 KB Output is correct
16 Correct 24 ms 5808 KB Output is correct
17 Correct 73 ms 11876 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 3677 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 116 ms 24172 KB Output is correct
3 Correct 111 ms 24060 KB Output is correct
4 Correct 106 ms 23108 KB Output is correct
5 Execution timed out 5076 ms 46952 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 736 ms 78528 KB Output is correct
3 Runtime error 3738 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 736 ms 78528 KB Output is correct
3 Runtime error 3738 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 736 ms 78528 KB Output is correct
3 Runtime error 3738 ms 524292 KB Execution killed with signal 9
4 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 Runtime error 2856 ms 524292 KB Execution killed with signal 9
3 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 Correct 44 ms 9600 KB Output is correct
3 Correct 69 ms 13768 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 972 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 32 ms 5352 KB Output is correct
16 Correct 24 ms 5808 KB Output is correct
17 Correct 73 ms 11876 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Runtime error 3677 ms 524292 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -