oj.uz

Submission #157932

# Submission time Handle Problem Language Result Execution time Memory
157932 2019-10-14T02:27:47 Z PeppaPig Strange Device (APIO19_strange_device) C++14
35 / 100
 883 ms 69104 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:37: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 384 KB Output is correct
2 Correct 9 ms 1268 KB Output is correct
3 Correct 9 ms 1268 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 9 ms 1396 KB Output is correct
17 Correct 80 ms 7268 KB Output is correct
18 Runtime error 2 ms 632 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 256 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 376 KB Output is correct
5 Correct 509 ms 57032 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 713 ms 69024 KB Output is correct
3 Correct 731 ms 69040 KB Output is correct
4 Correct 696 ms 68820 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 713 ms 69024 KB Output is correct
3 Correct 731 ms 69040 KB Output is correct
4 Correct 696 ms 68820 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 723 ms 68968 KB Output is correct
7 Correct 697 ms 68924 KB Output is correct
8 Correct 704 ms 68908 KB Output is correct
9 Correct 809 ms 69016 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 713 ms 69024 KB Output is correct
3 Correct 731 ms 69040 KB Output is correct
4 Correct 696 ms 68820 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 69 ms 7300 KB Output is correct
7 Correct 66 ms 7268 KB Output is correct
8 Correct 68 ms 7296 KB Output is correct
9 Correct 70 ms 7268 KB Output is correct
10 Correct 66 ms 7312 KB Output is correct
11 Correct 71 ms 7400 KB Output is correct
12 Correct 66 ms 7352 KB Output is correct
13 Correct 76 ms 7268 KB Output is correct
14 Correct 66 ms 7340 KB Output is correct
15 Correct 79 ms 7284 KB Output is correct
16 Correct 76 ms 7352 KB Output is correct
17 Correct 70 ms 7268 KB Output is correct
18 Correct 736 ms 68932 KB Output is correct
19 Correct 686 ms 68860 KB Output is correct
20 Correct 834 ms 68864 KB Output is correct
21 Correct 80 ms 7272 KB Output is correct
22 Correct 62 ms 7268 KB Output is correct
23 Correct 234 ms 26700 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 76 ms 7268 KB Output is correct
3 Correct 76 ms 7268 KB Output is correct
4 Correct 883 ms 69104 KB Output is correct
5 Correct 74 ms 7272 KB Output is correct
6 Correct 75 ms 7268 KB Output is correct
7 Correct 76 ms 7268 KB Output is correct
8 Correct 80 ms 7268 KB Output is correct
9 Correct 74 ms 7268 KB Output is correct
10 Correct 79 ms 7268 KB Output is correct
11 Correct 76 ms 7268 KB Output is correct
12 Correct 67 ms 7268 KB Output is correct
13 Correct 80 ms 7240 KB Output is correct
14 Correct 794 ms 68732 KB Output is correct
15 Correct 81 ms 7268 KB Output is correct
16 Correct 665 ms 69056 KB Output is correct
17 Correct 713 ms 69032 KB Output is correct
18 Runtime error 2 ms 468 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 384 KB Output is correct
2 Correct 9 ms 1268 KB Output is correct
3 Correct 9 ms 1268 KB Output is correct
4 Correct 2 ms 400 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 9 ms 1396 KB Output is correct
17 Correct 80 ms 7268 KB Output is correct
18 Runtime error 2 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)