oj.uz

Submission #931882

# Submission time Handle Problem Language Result Execution time Memory
931882 2024-02-22T14:02:44 Z 12345678 Strange Device (APIO19_strange_device) C++17
10 / 100
 645 ms 78828 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+1) 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 5 ms 3092 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Incorrect 1 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 2396 KB Output is correct
2 Correct 1 ms 2408 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 0 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 204 ms 15996 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 514 ms 78736 KB Output is correct
3 Incorrect 550 ms 78468 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 514 ms 78736 KB Output is correct
3 Incorrect 550 ms 78468 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 514 ms 78736 KB Output is correct
3 Incorrect 550 ms 78468 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 2392 KB Output is correct
2 Correct 52 ms 12880 KB Output is correct
3 Correct 56 ms 13036 KB Output is correct
4 Correct 604 ms 78672 KB Output is correct
5 Correct 61 ms 12880 KB Output is correct
6 Correct 54 ms 12784 KB Output is correct
7 Correct 54 ms 12880 KB Output is correct
8 Correct 54 ms 12892 KB Output is correct
9 Correct 50 ms 13036 KB Output is correct
10 Correct 48 ms 12892 KB Output is correct
11 Correct 48 ms 12800 KB Output is correct
12 Correct 51 ms 12888 KB Output is correct
13 Correct 56 ms 13036 KB Output is correct
14 Correct 645 ms 78828 KB Output is correct
15 Incorrect 53 ms 12884 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 5 ms 3092 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -