oj.uz

Submission #344511

# Submission time Handle Problem Language Result Execution time Memory
344511 2021-01-06T03:52:38 Z blue Strange Device (APIO19_strange_device) C++11
35 / 100
 1801 ms 17416 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long long_gcd(long long a, long long b)
{
    // cout << "gcd " << a << ' ' << b << '\n';
    if(a == b) return a;
    if(a < b) swap(a, b);
    if(b == 0) return a;
    return long_gcd(a%b, b);
}

long long long_abs(long long x)
{
    if(x >= 0) return x;
    return -x;
}

long long long_sign(long long x)
{
    if(x > 0) return 1;
    return -1;
}

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


    long long period = A * B / long_gcd(A, B+1);

    // cout << period << '\n';

    long long l, r;

    vector<long long> endpoints;

    long long maxSize = 0;

    for(int i = 1; i <= n; i++)
    {
        cin >> l >> r;
        maxSize = max(maxSize, r-l+1);

        if(l % period <= r % period)
        {
            endpoints.push_back(l % period + 1);
            endpoints.push_back(-(r % period) - 1 - 1);
        }
        else
        {
            endpoints.push_back(l % period + 1);
            endpoints.push_back(-period - 1);

            endpoints.push_back(0 + 1);
            endpoints.push_back(-(r % period) - 1 - 1);
        }
    }

    if(maxSize >= period)
    {
        cout << period << '\n';
        return 0;
    }


        // for(long long e: endpoints) cout << e << ' ';
        // cout << '\n';


    sort(endpoints.begin(), endpoints.end(), [] (long long p, long long q)
    {
        return long_abs(p) < long_abs(q);
    });

    // for(long long e: endpoints) cout << e << ' ';
    // cout << '\n';


    long long res = 0;

    long long count = 0;
    count += long_sign(endpoints[0]);
    for(int i = 1; i < endpoints.size(); i++)
    {
        // cout << count << ' ' << long_abs(endpoints[i]) - long_abs(endpoints[i-1]) << '\n';
        if(count > 0) res += long_abs(endpoints[i]) - long_abs(endpoints[i-1]);
        count += long_sign(endpoints[i]);
    }

    cout << res << '\n';
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 1; i < endpoints.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 20 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 16 ms 876 KB Output is correct
17 Correct 184 ms 2656 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1119 ms 17128 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1626 ms 16968 KB Output is correct
3 Correct 1724 ms 17116 KB Output is correct
4 Correct 1616 ms 17096 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1626 ms 16968 KB Output is correct
3 Correct 1724 ms 17116 KB Output is correct
4 Correct 1616 ms 17096 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1649 ms 16968 KB Output is correct
7 Correct 1603 ms 16968 KB Output is correct
8 Correct 1633 ms 17112 KB Output is correct
9 Correct 1801 ms 16968 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1626 ms 16968 KB Output is correct
3 Correct 1724 ms 17116 KB Output is correct
4 Correct 1616 ms 17096 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 158 ms 2656 KB Output is correct
7 Correct 165 ms 2656 KB Output is correct
8 Correct 154 ms 2656 KB Output is correct
9 Correct 158 ms 2656 KB Output is correct
10 Correct 156 ms 2912 KB Output is correct
11 Correct 163 ms 2656 KB Output is correct
12 Correct 156 ms 2560 KB Output is correct
13 Correct 171 ms 2656 KB Output is correct
14 Correct 155 ms 2656 KB Output is correct
15 Correct 170 ms 2656 KB Output is correct
16 Correct 167 ms 2656 KB Output is correct
17 Correct 156 ms 2656 KB Output is correct
18 Correct 1616 ms 17416 KB Output is correct
19 Correct 1576 ms 16992 KB Output is correct
20 Correct 1760 ms 17236 KB Output is correct
21 Correct 172 ms 2656 KB Output is correct
22 Correct 152 ms 2656 KB Output is correct
23 Correct 493 ms 8728 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 169 ms 2636 KB Output is correct
3 Correct 173 ms 2656 KB Output is correct
4 Correct 1797 ms 16968 KB Output is correct
5 Correct 171 ms 2656 KB Output is correct
6 Correct 168 ms 2656 KB Output is correct
7 Correct 167 ms 2656 KB Output is correct
8 Correct 173 ms 2784 KB Output is correct
9 Correct 167 ms 2656 KB Output is correct
10 Correct 171 ms 2656 KB Output is correct
11 Correct 167 ms 2656 KB Output is correct
12 Correct 162 ms 2656 KB Output is correct
13 Correct 172 ms 2656 KB Output is correct
14 Correct 1762 ms 16968 KB Output is correct
15 Correct 175 ms 2692 KB Output is correct
16 Correct 1580 ms 17240 KB Output is correct
17 Correct 1617 ms 17096 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 876 KB Output is correct
3 Correct 20 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 372 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 16 ms 876 KB Output is correct
17 Correct 184 ms 2656 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct