oj.uz

Submission #332968

# Submission time Handle Problem Language Result Execution time Memory
332968 2020-12-04T05:12:09 Z leinad2 Strange Device (APIO19_strange_device) C++14
15 / 100
 288 ms 83552 KB 
#include<bits/stdc++.h>
#define int __int128
using namespace std;
int n, i, j, k, a, b, x, A[500010][2], ans;
int gcd(int a, int b)
{
    if(b==0)return a;
    return gcd(b, a%b);
}
vector<pair<int, int> >v, V;
main()
{
    for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
    x=(a*b)/(gcd(a, b+1));
    for(i=0;i++<n;)
    {
        if(A[i][1]-A[i][0]>=x-1)
        {
            v.push_back({0, x-1});
        }
        else
        {
            if(A[i][0]%x<=A[i][1]%x)
            {
                v.push_back({A[i][0]%x, A[i][1]%x});
            }
            else
            {
                v.push_back({0, A[i][1]%x});
                v.push_back({A[i][0]%x, x-1});
            }
        }
    }
    sort(v.begin(), v.end());
    for(i=0;i<v.size();i++)
    {
        if(V.size()==0)V.push_back(v[i]);
        else
        {
            if(V.back().second>=v[i].first)
            {
                if(V.back().second<v[i].second)
                {
                    V.back().second=v[i].second;
                }
            }
            else
            {
                V.push_back(v[i]);
            }
        }
    }
    for(i=0;i<V.size();i++)
    {
        ans+=(V[i].second-V[i].first+1);
    }
    printf("%lld", ans);
}

Compilation message

strange_device.cpp:11:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main()
      |      ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:13:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type '__int128*' [-Wformat=]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                ~~~^             ~~
      |                   |             |
      |                   |             __int128*
      |                   long long int*
strange_device.cpp:13:24: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type '__int128*' [-Wformat=]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                     ~~~^            ~~
      |                        |            |
      |                        |            __int128*
      |                        long long int*
strange_device.cpp:13:29: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type '__int128*' [-Wformat=]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                          ~~~^           ~~
      |                             |           |
      |                             |           __int128*
      |                             long long int*
strange_device.cpp:13:62: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type '__int128*' [-Wformat=]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                                                           ~~~^        ~~~~~~~~
      |                                                              |        |
      |                                                              |        __int128*
      |                                                              long long int*
strange_device.cpp:13:67: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type '__int128*' [-Wformat=]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                                                                ~~~^             ~~~~~~~~
      |                                                                   |             |
      |                                                                   |             __int128*
      |                                                                   long long int*
strange_device.cpp:57:16: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__int128' [-Wformat=]
   57 |     printf("%lld", ans);
      |             ~~~^   ~~~
      |                |   |
      |                |   __int128
      |                long long int
strange_device.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:13:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     for(scanf("%lld %lld %lld", &n, &a, &b);i++<n;)scanf("%lld %lld", &A[i][0], &A[i][1]);
      |                                                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 2148 KB Output is correct
3 Correct 7 ms 2148 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 2148 KB Output is correct
17 Correct 69 ms 16472 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Runtime error 259 ms 77380 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 288 ms 83552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 288 ms 83552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 288 ms 83552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 66 ms 16512 KB Output is correct
3 Correct 68 ms 16600 KB Output is correct
4 Runtime error 282 ms 83508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 7 ms 2148 KB Output is correct
3 Correct 7 ms 2148 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 7 ms 2148 KB Output is correct
17 Correct 69 ms 16472 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 492 KB Output is correct
28 Runtime error 259 ms 77380 KB Execution killed with signal 11 (could be triggered by violating memory limits)