oj.uz

Submission #649796

# Submission time Handle Problem Language Result Execution time Memory
649796 2022-10-11T10:57:53 Z ToroTN Strange Device (APIO19_strange_device) C++14
65 / 100
 457 ms 16948 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second
#define pb push_back
ll n,a,b,x,y,md,cnt=0,mx=-1,l,r,di;
set<pair<ll,ll> > s;
vector<pair<ll,ll> > v;
ll gcdprajao(ll a,ll b)
{
    if(b==0)return a;
    return gcdprajao(b,a%b);
}
int main()
{
    scanf("%lld%lld%lld",&n,&a,&b);
    di=a/gcdprajao(b+1,a);
    if((double)di>(double)(1e18+1)/b)
    {
        md=1e18+1;
    }else
    {
        md=di*b;
    }
    //printf("%lld\n",md);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x,&y);
        if(x!=0)x%=md;
        if(y!=0)y%=md;
        if(x<=y)
        {
            v.pb({x,y});
        }else
        {
            v.pb({x,md-1});
            v.pb({0,y});
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        l=v[i].X;
        r=v[i].Y;
        if(l>mx)
        {
            cnt+=(r-l+1);
            mx=r;
        }else
        {
            if(r>mx)
            {
                cnt+=r-mx;
                mx=r;
            }
        }
    }
    printf("%lld\n",cnt);
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:42: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]
   42 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
strange_device.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%lld%lld%lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%lld%lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 44 ms 2376 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 301 ms 16760 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 442 ms 16724 KB Output is correct
3 Correct 381 ms 16808 KB Output is correct
4 Correct 384 ms 16848 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 442 ms 16724 KB Output is correct
3 Correct 381 ms 16808 KB Output is correct
4 Correct 384 ms 16848 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 418 ms 16864 KB Output is correct
7 Correct 434 ms 16780 KB Output is correct
8 Correct 388 ms 16804 KB Output is correct
9 Correct 440 ms 16724 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 442 ms 16724 KB Output is correct
3 Correct 381 ms 16808 KB Output is correct
4 Correct 384 ms 16848 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 39 ms 2376 KB Output is correct
7 Correct 42 ms 2484 KB Output is correct
8 Correct 44 ms 2432 KB Output is correct
9 Correct 41 ms 2384 KB Output is correct
10 Correct 40 ms 2392 KB Output is correct
11 Correct 40 ms 2376 KB Output is correct
12 Correct 40 ms 2448 KB Output is correct
13 Correct 46 ms 2484 KB Output is correct
14 Correct 44 ms 2432 KB Output is correct
15 Correct 42 ms 2432 KB Output is correct
16 Correct 42 ms 2408 KB Output is correct
17 Correct 39 ms 2472 KB Output is correct
18 Correct 392 ms 16796 KB Output is correct
19 Correct 394 ms 16948 KB Output is correct
20 Correct 433 ms 16804 KB Output is correct
21 Correct 45 ms 2380 KB Output is correct
22 Correct 39 ms 2400 KB Output is correct
23 Correct 121 ms 8632 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 42 ms 2368 KB Output is correct
3 Correct 43 ms 2436 KB Output is correct
4 Correct 457 ms 16812 KB Output is correct
5 Correct 43 ms 2368 KB Output is correct
6 Correct 42 ms 2476 KB Output is correct
7 Correct 43 ms 2440 KB Output is correct
8 Correct 41 ms 2396 KB Output is correct
9 Correct 41 ms 2412 KB Output is correct
10 Correct 41 ms 2376 KB Output is correct
11 Correct 42 ms 2392 KB Output is correct
12 Correct 37 ms 2488 KB Output is correct
13 Correct 43 ms 2448 KB Output is correct
14 Correct 428 ms 16732 KB Output is correct
15 Correct 42 ms 2376 KB Output is correct
16 Correct 452 ms 16736 KB Output is correct
17 Correct 416 ms 16824 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 7 ms 596 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 5 ms 596 KB Output is correct
17 Correct 44 ms 2376 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Incorrect 0 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -