oj.uz

Submission #154804

# Submission time Handle Problem Language Result Execution time Memory
154804 2019-09-24T18:00:10 Z Akashi Strange Device (APIO19_strange_device) C++14
10 / 100
 2843 ms 16884 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;

    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 29 ms 892 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 1857 ms 16576 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2629 ms 16840 KB Output is correct
3 Incorrect 2843 ms 16884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2629 ms 16840 KB Output is correct
3 Incorrect 2843 ms 16884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2629 ms 16840 KB Output is correct
3 Incorrect 2843 ms 16884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 291 ms 5628 KB Output is correct
3 Correct 268 ms 5596 KB Output is correct
4 Correct 2703 ms 16676 KB Output is correct
5 Correct 271 ms 5688 KB Output is correct
6 Correct 274 ms 5584 KB Output is correct
7 Correct 288 ms 5624 KB Output is correct
8 Correct 276 ms 5540 KB Output is correct
9 Correct 273 ms 5568 KB Output is correct
10 Correct 271 ms 5572 KB Output is correct
11 Correct 268 ms 5608 KB Output is correct
12 Correct 265 ms 5596 KB Output is correct
13 Correct 270 ms 5624 KB Output is correct
14 Correct 2679 ms 16784 KB Output is correct
15 Incorrect 269 ms 5752 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 29 ms 892 KB Output is correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Halted 0 ms 0 KB -