oj.uz

Submission #154803

# Submission time Handle Problem Language Result Execution time Memory
154803 2019-09-24T17:55:47 Z Akashi Strange Device (APIO19_strange_device) C++14
10 / 100
 2703 ms 16548 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 = -2, r = -3;
    for(int i = 1; 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 376 KB Output is correct
2 Correct 28 ms 888 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Incorrect 2 ms 256 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 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 1846 ms 16312 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 2614 ms 16548 KB Output is correct
3 Incorrect 2629 ms 16400 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 2614 ms 16548 KB Output is correct
3 Incorrect 2629 ms 16400 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 2614 ms 16548 KB Output is correct
3 Incorrect 2629 ms 16400 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 376 KB Output is correct
2 Correct 268 ms 5792 KB Output is correct
3 Correct 268 ms 5756 KB Output is correct
4 Correct 2703 ms 16476 KB Output is correct
5 Correct 268 ms 5496 KB Output is correct
6 Correct 275 ms 5332 KB Output is correct
7 Correct 276 ms 5296 KB Output is correct
8 Correct 272 ms 5356 KB Output is correct
9 Correct 271 ms 5416 KB Output is correct
10 Correct 269 ms 5484 KB Output is correct
11 Correct 270 ms 5368 KB Output is correct
12 Correct 262 ms 5292 KB Output is correct
13 Correct 270 ms 5368 KB Output is correct
14 Correct 2682 ms 16456 KB Output is correct
15 Incorrect 273 ms 5516 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 376 KB Output is correct
2 Correct 28 ms 888 KB Output is correct
3 Correct 28 ms 888 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -