oj.uz

Submission #729694

# Submission time Handle Problem Language Result Execution time Memory
729694 2023-04-24T11:17:47 Z danikoynov Strange Device (APIO19_strange_device) C++14
5 / 100
 5000 ms 48948 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e6 + 10;

int n;
ll l[maxn], r[maxn];
ll A, B;

struct point
{
    ll x, t;
    point(ll _x = 0, ll _t = 0)
    {
        x = _x;
        t = _t;
    }

    bool operator < (const point &p) const
    {
        if (x == p.x)
            return t < p.t;
        return x < p.x;
    }
};


vector < point > vec;
void add_segment(int l, int r)
{

    vec.push_back(point(l, 1));
    vec.push_back(point(r, -1));
}
void solve()
{
    cin >> n >> A >> B;

    for (int i = 1; i <= n; i ++)
    {
        cin >> l[i] >> r[i];
    }
    ll g = __gcd(A, B + 1);
    /// period is A * B / g
    if ((double)(1e18) / (double)(A) < (double)(B) / (double)(g))
    {
        while(true);
        ll ans = 0;
        for (int i = 1; i <= n; i ++)
        {
            ans = ans + (r[i] - l[i] + 1);
        }
        cout << ans << endl;
        return;
    }

    long long period = (A / g) * B;
    for (int i = 1; i <= n; i ++)
    {


            if (r[i] - l[i] + 1 >= period)
            {
                cout << period << endl;
                return;
            }

            r[i] ++;
            ll x = l[i] % period, y = r[i] % period;
            if (x <= y)
            {
                add_segment(x, y);
            }
            else
            {
                add_segment(0, y);
                add_segment(x, period);
            }

    }

    sort(vec.begin(), vec.end());
    ll ans = 0, cnt = 0;
    for (int i = 0; i < vec.size();)
    {
        int r = i;
        while(r < vec.size() && vec[i].x == vec[r].x)
            r ++;
        for (int j = i; j < r; j ++)
            cnt += vec[j].t;
            //cout << i << " : " << r << " " << cnt << " " << vec[r].x << " " << vec[i].x << endl;
        if (cnt > 0)
            ans = ans + vec[r].x - vec[i].x;
        i = r;
    }
    cout << ans << endl;
}


int main()
{
    solve();
    return 0;
}
/**
1  10000 3312452154131231
1 1
*/

Compilation message

strange_device.cpp: In function 'void solve()':
strange_device.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < vec.size();)
      |                     ~~^~~~~~~~~~~~
strange_device.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         while(r < vec.size() && vec[i].x == vec[r].x)
      |               ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct
3 Correct 14 ms 1104 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1072 KB Output is correct
17 Correct 144 ms 6012 KB Output is correct
18 Execution timed out 5068 ms 212 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Execution timed out 5033 ms 212 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 979 ms 48948 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1398 ms 48884 KB Output is correct
3 Incorrect 1318 ms 48908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1398 ms 48884 KB Output is correct
3 Incorrect 1318 ms 48908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1398 ms 48884 KB Output is correct
3 Incorrect 1318 ms 48908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 149 ms 6116 KB Output is correct
3 Incorrect 154 ms 6028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct
3 Correct 14 ms 1104 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 14 ms 1072 KB Output is correct
17 Correct 144 ms 6012 KB Output is correct
18 Execution timed out 5068 ms 212 KB Time limit exceeded
19 Halted 0 ms 0 KB -