oj.uz

Submission #120780

# Submission time Handle Problem Language Result Execution time Memory
120780 2019-06-25T13:12:51 Z PeppaPig Strange Device (APIO19_strange_device) C++14
35 / 100
 889 ms 33432 KB 
#include <bits/stdc++.h>

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

const int N = 1e6+5;

int n;
long A, B, cyc;
vector<pii> v;

int main() {
    scanf("%d %lld %lld", &n, &A, &B);
    cyc = A / __gcd(B+1, A);
    cyc *= B;

    for(int i = 1; i <= n; i++) {
        long l, r;
        scanf("%lld %lld", &l, &r);
        if(r - l + 1 >= cyc) v.emplace_back(0, 1), v.emplace_back(cyc, -1);
        else {
            l %= cyc, r %= cyc;
            v.emplace_back(l, 1);
            v.emplace_back(r + 1, -1); 
            if(l > r) v.emplace_back(0, 1), v.emplace_back(cyc, -1);
        }
    }
    sort(v.begin(), v.end());
    long ans = 0;
    for(int i = 0, cnt = 0; i < v.size(); ) {
        int j = i;
        for( ; v[i].x == v[j].x; j++) cnt += v[j].y;
        if(cnt) ans += v[j].x - v[i].x;
        i = j;
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:34:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0, cnt = 0; i < v.size(); ) {
                             ~~^~~~~~~~~~
strange_device.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld %lld", &n, &A, &B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 1012 KB Output is correct
3 Correct 9 ms 1012 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 280 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1012 KB Output is correct
17 Correct 77 ms 4584 KB Output is correct
18 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
5 Correct 528 ms 33220 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 666 ms 33312 KB Output is correct
3 Correct 701 ms 33256 KB Output is correct
4 Correct 676 ms 33264 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 666 ms 33312 KB Output is correct
3 Correct 701 ms 33256 KB Output is correct
4 Correct 676 ms 33264 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 689 ms 33316 KB Output is correct
7 Correct 651 ms 33288 KB Output is correct
8 Correct 683 ms 33252 KB Output is correct
9 Correct 818 ms 33336 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 666 ms 33312 KB Output is correct
3 Correct 701 ms 33256 KB Output is correct
4 Correct 676 ms 33264 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 65 ms 4552 KB Output is correct
7 Correct 68 ms 4552 KB Output is correct
8 Correct 65 ms 4588 KB Output is correct
9 Correct 70 ms 4580 KB Output is correct
10 Correct 63 ms 4580 KB Output is correct
11 Correct 68 ms 4588 KB Output is correct
12 Correct 66 ms 4584 KB Output is correct
13 Correct 75 ms 4584 KB Output is correct
14 Correct 66 ms 4496 KB Output is correct
15 Correct 76 ms 4508 KB Output is correct
16 Correct 73 ms 4568 KB Output is correct
17 Correct 68 ms 4580 KB Output is correct
18 Correct 694 ms 33212 KB Output is correct
19 Correct 643 ms 33244 KB Output is correct
20 Correct 820 ms 33252 KB Output is correct
21 Correct 77 ms 4572 KB Output is correct
22 Correct 60 ms 4580 KB Output is correct
23 Correct 233 ms 16864 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 72 ms 4484 KB Output is correct
3 Correct 74 ms 4580 KB Output is correct
4 Correct 889 ms 33432 KB Output is correct
5 Correct 75 ms 4580 KB Output is correct
6 Correct 71 ms 4708 KB Output is correct
7 Correct 75 ms 4584 KB Output is correct
8 Correct 77 ms 4552 KB Output is correct
9 Correct 72 ms 4652 KB Output is correct
10 Correct 77 ms 4580 KB Output is correct
11 Correct 74 ms 4552 KB Output is correct
12 Correct 68 ms 4580 KB Output is correct
13 Correct 77 ms 4580 KB Output is correct
14 Correct 778 ms 33320 KB Output is correct
15 Correct 77 ms 4552 KB Output is correct
16 Correct 637 ms 33332 KB Output is correct
17 Correct 678 ms 33340 KB Output is correct
18 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 1012 KB Output is correct
3 Correct 9 ms 1012 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 280 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1012 KB Output is correct
17 Correct 77 ms 4584 KB Output is correct
18 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)