oj.uz

Submission #931878

# Submission time Handle Problem Language Result Execution time Memory
931878 2024-02-22T13:56:59 Z 12345678 Strange Device (APIO19_strange_device) C++17
10 / 100
 459 ms 79016 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;
ll n, a, b, l[nx], r[nx], sm, p, mx, res;
set<pair<ll, ll>> s;

void add_range(ll x, ll y)
{
    x=x%p;
    y=y%p;
    if (y<x) y+=p;
    s.insert({x, min(p-1, y)});
    if (y>=p) s.insert({0, y-p});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a>>b;
    p=a*b;
    for (int i=1; i<=n; i++) cin>>l[i]>>r[i], mx=max(mx, r[i]-l[i]+1), sm+=(r[i]-l[i]+1);
    if (a>LLONG_MAX/b) return cout<<sm, 0;
    if (mx>=p) return cout<<p, 0;
    for (int i=1; i<=n; i++) add_range(l[i], r[i]);
    for (auto itr=s.begin(); itr!=s.end()&&next(itr)!=s.end();)
    {
        auto itr2=next(itr);
        pair<ll, ll> nw;
        if (itr2->first>itr->second) itr=itr2;
        else nw={itr->first, max(itr->second, itr2->second)}, s.erase(itr), s.erase(itr2), s.insert(nw), itr=s.find(nw);
    }
    for (auto [x, y]:s) res+=y-x+1;
    cout<<res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 4 ms 3164 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Incorrect 0 ms 2396 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 182 ms 15956 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 419 ms 78712 KB Output is correct
3 Incorrect 435 ms 79016 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 2396 KB Output is correct
2 Correct 419 ms 78712 KB Output is correct
3 Incorrect 435 ms 79016 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 2396 KB Output is correct
2 Correct 419 ms 78712 KB Output is correct
3 Incorrect 435 ms 79016 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 2396 KB Output is correct
2 Correct 44 ms 12808 KB Output is correct
3 Correct 43 ms 13052 KB Output is correct
4 Correct 439 ms 78872 KB Output is correct
5 Correct 40 ms 12888 KB Output is correct
6 Correct 41 ms 12888 KB Output is correct
7 Correct 39 ms 12884 KB Output is correct
8 Correct 40 ms 12884 KB Output is correct
9 Correct 40 ms 12904 KB Output is correct
10 Correct 38 ms 12884 KB Output is correct
11 Correct 42 ms 13140 KB Output is correct
12 Correct 39 ms 13016 KB Output is correct
13 Correct 40 ms 12892 KB Output is correct
14 Correct 459 ms 78676 KB Output is correct
15 Incorrect 40 ms 12880 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 4 ms 3164 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Incorrect 0 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -