oj.uz

Submission #154805

# Submission time Handle Problem Language Result Execution time Memory
154805 2019-09-24T18:08:27 Z Akashi Strange Device (APIO19_strange_device) C++14
35 / 100
 3225 ms 53284 KB 
#include <bits/stdc++.h>
using namespace std;

struct interv{
    long long l, r;
    bool operator < (const interv &aux)const{
        if(l != aux.l) return l < aux.l;
        return r < aux.r;
    }
};

interv a[2000005];

int n;
long long A, B;

int main()
{
    cin >> n >> A >> B;

    double lg1 = log2((double)A), lg2 = log2((double)B);
    long long prod = 0;
    if(lg1 + lg2 <= 63) prod = 1LL * A * B;

    if(A != 1 && B == 1 && A % 2 == 0) prod = A / 2;

    int m = n;
    for(int i = 1; i <= n ; ++i){
        cin >> a[i].l >> a[i].r;
        if(prod != 0){
            if(a[i].r - a[i].l + 1 >= prod){
                a[i].l = 0; a[i].r = prod - 1;
                continue ;
            }
            a[i].l %= prod, a[i].r %= prod;
            if(a[i].r < a[i].l) a[++m].l = 0, a[m].r = a[i].r, a[i].r = prod - 1;
        }
    }

    n = m;

    sort(a + 1, a + n + 1);

    long long Sol = 0, l = a[1].l, r = a[1].r;
    for(int i = 2; i <= n ; ++i){
        if(r < a[i].l){
            Sol = Sol + (r - l + 1);
            l = a[i].l; r = a[i].r;
        }
        else r = max(r, a[i].r);
    }

    Sol = Sol + (r - l + 1);

    cout << Sol;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 29 ms 888 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.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 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 424 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 1857 ms 17056 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 2629 ms 17752 KB Output is correct
3 Correct 2620 ms 17732 KB Output is correct
4 Correct 2679 ms 53164 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2629 ms 17752 KB Output is correct
3 Correct 2620 ms 17732 KB Output is correct
4 Correct 2679 ms 53164 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2655 ms 53192 KB Output is correct
7 Correct 2632 ms 53108 KB Output is correct
8 Incorrect 2680 ms 53140 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2629 ms 17752 KB Output is correct
3 Correct 2620 ms 17732 KB Output is correct
4 Correct 2679 ms 53164 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 262 ms 5660 KB Output is correct
7 Correct 268 ms 5708 KB Output is correct
8 Correct 264 ms 5560 KB Output is correct
9 Correct 267 ms 5724 KB Output is correct
10 Correct 270 ms 5676 KB Output is correct
11 Correct 267 ms 5740 KB Output is correct
12 Correct 267 ms 5672 KB Output is correct
13 Correct 272 ms 5624 KB Output is correct
14 Correct 266 ms 5680 KB Output is correct
15 Correct 294 ms 5624 KB Output is correct
16 Correct 269 ms 5624 KB Output is correct
17 Correct 266 ms 5752 KB Output is correct
18 Correct 2631 ms 53196 KB Output is correct
19 Correct 2628 ms 53140 KB Output is correct
20 Correct 2688 ms 53284 KB Output is correct
21 Correct 267 ms 5580 KB Output is correct
22 Correct 264 ms 5624 KB Output is correct
23 Correct 876 ms 18252 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 268 ms 5664 KB Output is correct
3 Correct 267 ms 5600 KB Output is correct
4 Correct 2695 ms 18412 KB Output is correct
5 Correct 268 ms 5624 KB Output is correct
6 Correct 268 ms 5640 KB Output is correct
7 Correct 271 ms 5624 KB Output is correct
8 Correct 275 ms 5644 KB Output is correct
9 Correct 272 ms 5732 KB Output is correct
10 Correct 269 ms 5684 KB Output is correct
11 Correct 270 ms 5596 KB Output is correct
12 Correct 260 ms 5624 KB Output is correct
13 Correct 274 ms 5676 KB Output is correct
14 Correct 3225 ms 18308 KB Output is correct
15 Incorrect 280 ms 5784 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 29 ms 888 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -