oj.uz

Submission #344503

# Submission time Handle Problem Language Result Execution time Memory
344503 2021-01-06T03:23:40 Z blue Strange Device (APIO19_strange_device) C++11
0 / 100
 5000 ms 364 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
Observations:

(1, b) = b

(b+1, b) = b

If a is even,      (a, 1) = a/2
Else if a is odd,  (a, 1) = a

b divides (a, b)

If b+1 divides a


If a and b+1 are coprime (a, b) = a*b

a*b / gcd(a, b+1) = ;

lcm(a, b+1) - a
*/

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;

    if(n == 1)
    {
        cin >> l >> r;

        if(r-l+1 >= period)
        {
            while(1);
        }
        if(l % period <= r % period)
        {
            cout << (r % period) - (l % period) + 1 << '\n';
        }
        else
        {
            cout << period - ((r % period) - (l % period) + 1) + 2 << '\n';
        }
        return 0;
    }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5070 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5086 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5086 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5086 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5070 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -