oj.uz

Submission #405037

# Submission time Handle Problem Language Result Execution time Memory
405037 2021-05-15T15:48:23 Z A_D Strange Device (APIO19_strange_device) C++14
65 / 100
 604 ms 72388 KB 
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=1e6+100;
ii a[N];
vector<int> l;
vector<int> r;
vector<ii> b;
set<ii> st;

void solve()
{
    int n,A,B,m=1e18+10;
    cin>>n>>A>>B;
    B++;
    du aa=A;
    du bb=B;
    du sum=aa*bb;
    du q=__gcd(A,B);
    du lcm=sum/q;
    lcm/=B;
    lcm*=B-1;
    if(lcm<=1e18){
        m=lcm;
    }
//    cout<<m<<endl;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].F);
        scanf("%lld",&a[i].S);
        a[i].F%=m;
        a[i].S%=m;
        if(a[i].S<a[i].F){
            b.push_back({a[i].F,m-1});
            b.push_back({(int)0,a[i].S});
        }
        else{
            b.push_back({a[i].F,a[i].S});
        }
    }
    sort(b.begin(),b.end());
    l.push_back(b[0].F);
    r.push_back(b[0].S);
    for(int i=1;i<b.size();i++){
        int ll=l.back();
        int rr=r.back();
        if(!(ll>b[i].S||rr<b[i].F)){
            l.pop_back();
            r.pop_back();
            l.push_back(min(ll,b[i].F));
            r.push_back(max(rr,b[i].S));
        }
        else{
            l.push_back(b[i].F);
            r.push_back(b[i].S);
        }
    }
    int ans=0;
    for(int i=0;i<l.size();i++){
        //cout<<l[i]<<" "<<r[i]<<endl;
        ans+=r[i]-l[i]+1;
    }
    cout<<ans<<endl;
}
main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:47:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=1;i<b.size();i++){
      |                 ~^~~~~~~~~
strange_device.cpp:62:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
strange_device.cpp: At global scope:
strange_device.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main()
      | ^~~~
strange_device.cpp: In function 'void solve()':
strange_device.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%lld",&a[i].F);
      |         ~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%lld",&a[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 7 ms 840 KB Output is correct
3 Correct 6 ms 840 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 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 204 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 6 ms 1252 KB Output is correct
17 Correct 57 ms 6704 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 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 380 ms 31748 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 532 ms 53012 KB Output is correct
3 Correct 529 ms 53128 KB Output is correct
4 Correct 527 ms 53072 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 532 ms 53012 KB Output is correct
3 Correct 529 ms 53128 KB Output is correct
4 Correct 527 ms 53072 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 523 ms 53080 KB Output is correct
7 Correct 549 ms 53284 KB Output is correct
8 Correct 536 ms 53136 KB Output is correct
9 Correct 554 ms 53136 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 532 ms 53012 KB Output is correct
3 Correct 529 ms 53128 KB Output is correct
4 Correct 527 ms 53072 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 53 ms 6296 KB Output is correct
7 Correct 55 ms 6724 KB Output is correct
8 Correct 53 ms 6780 KB Output is correct
9 Correct 53 ms 6704 KB Output is correct
10 Correct 52 ms 6648 KB Output is correct
11 Correct 53 ms 6700 KB Output is correct
12 Correct 50 ms 6700 KB Output is correct
13 Correct 58 ms 6700 KB Output is correct
14 Correct 57 ms 6636 KB Output is correct
15 Correct 57 ms 6744 KB Output is correct
16 Correct 59 ms 6888 KB Output is correct
17 Correct 56 ms 6728 KB Output is correct
18 Correct 523 ms 53144 KB Output is correct
19 Correct 519 ms 72332 KB Output is correct
20 Correct 565 ms 72292 KB Output is correct
21 Correct 60 ms 10032 KB Output is correct
22 Correct 53 ms 10044 KB Output is correct
23 Correct 187 ms 23620 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 58 ms 6268 KB Output is correct
3 Correct 59 ms 6368 KB Output is correct
4 Correct 604 ms 53224 KB Output is correct
5 Correct 55 ms 6324 KB Output is correct
6 Correct 56 ms 6348 KB Output is correct
7 Correct 58 ms 6336 KB Output is correct
8 Correct 59 ms 6348 KB Output is correct
9 Correct 54 ms 6296 KB Output is correct
10 Correct 56 ms 6320 KB Output is correct
11 Correct 55 ms 6368 KB Output is correct
12 Correct 49 ms 6320 KB Output is correct
13 Correct 55 ms 6300 KB Output is correct
14 Correct 551 ms 53132 KB Output is correct
15 Correct 55 ms 6188 KB Output is correct
16 Correct 531 ms 72304 KB Output is correct
17 Correct 524 ms 72388 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 840 KB Output is correct
3 Correct 6 ms 840 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 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 204 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 6 ms 1252 KB Output is correct
17 Correct 57 ms 6704 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -