oj.uz

Submission #346909

# Submission time Handle Problem Language Result Execution time Memory
346909 2021-01-11T10:24:44 Z blue Strange Device (APIO19_strange_device) C++11
65 / 100
 1838 ms 21872 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) 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;

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

        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);
        }
    }


        // 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:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 1; i < endpoints.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 17 ms 1004 KB Output is correct
3 Correct 17 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 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 18 ms 1132 KB Output is correct
17 Correct 174 ms 5724 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 5.0

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

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 384 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1074 ms 21608 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 1594 ms 18504 KB Output is correct
3 Correct 1657 ms 21492 KB Output is correct
4 Correct 1604 ms 21356 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 1594 ms 18504 KB Output is correct
3 Correct 1657 ms 21492 KB Output is correct
4 Correct 1604 ms 21356 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1623 ms 21448 KB Output is correct
7 Correct 1607 ms 21544 KB Output is correct
8 Correct 1608 ms 21704 KB Output is correct
9 Correct 1750 ms 21712 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 1594 ms 18504 KB Output is correct
3 Correct 1657 ms 21492 KB Output is correct
4 Correct 1604 ms 21356 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 162 ms 5780 KB Output is correct
7 Correct 171 ms 5724 KB Output is correct
8 Correct 167 ms 5724 KB Output is correct
9 Correct 162 ms 5724 KB Output is correct
10 Correct 157 ms 5724 KB Output is correct
11 Correct 163 ms 5768 KB Output is correct
12 Correct 159 ms 5724 KB Output is correct
13 Correct 176 ms 5756 KB Output is correct
14 Correct 155 ms 5912 KB Output is correct
15 Correct 178 ms 5724 KB Output is correct
16 Correct 170 ms 5724 KB Output is correct
17 Correct 162 ms 5712 KB Output is correct
18 Correct 1637 ms 21872 KB Output is correct
19 Correct 1594 ms 21704 KB Output is correct
20 Correct 1838 ms 21608 KB Output is correct
21 Correct 173 ms 5724 KB Output is correct
22 Correct 153 ms 5724 KB Output is correct
23 Correct 495 ms 12916 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 168 ms 5728 KB Output is correct
3 Correct 170 ms 5724 KB Output is correct
4 Correct 1803 ms 21328 KB Output is correct
5 Correct 172 ms 5852 KB Output is correct
6 Correct 169 ms 5724 KB Output is correct
7 Correct 170 ms 5872 KB Output is correct
8 Correct 173 ms 5724 KB Output is correct
9 Correct 166 ms 5724 KB Output is correct
10 Correct 175 ms 5724 KB Output is correct
11 Correct 169 ms 5724 KB Output is correct
12 Correct 158 ms 5724 KB Output is correct
13 Correct 177 ms 5724 KB Output is correct
14 Correct 1832 ms 21080 KB Output is correct
15 Correct 175 ms 5708 KB Output is correct
16 Correct 1599 ms 21576 KB Output is correct
17 Correct 1624 ms 21524 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 17 ms 1004 KB Output is correct
3 Correct 17 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 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 18 ms 1132 KB Output is correct
17 Correct 174 ms 5724 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -