oj.uz

Submission #932774

# Submission time Handle Problem Language Result Execution time Memory
932774 2024-02-24T07:41:44 Z 12345678 Strange Device (APIO19_strange_device) C++17
10 / 100
 727 ms 116076 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-1)/b+1) 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 [x, y]:s) cout<<"val "<<x<<' '<<y<<'\n';
    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 3420 KB Output is correct
3 Correct 6 ms 3592 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 2 ms 2512 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 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 2528 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 190 ms 41044 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 515 ms 115680 KB Output is correct
3 Incorrect 559 ms 115832 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 2392 KB Output is correct
2 Correct 515 ms 115680 KB Output is correct
3 Incorrect 559 ms 115832 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 2392 KB Output is correct
2 Correct 515 ms 115680 KB Output is correct
3 Incorrect 559 ms 115832 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 55 ms 16620 KB Output is correct
3 Correct 55 ms 16724 KB Output is correct
4 Correct 633 ms 116076 KB Output is correct
5 Correct 55 ms 16748 KB Output is correct
6 Correct 59 ms 16724 KB Output is correct
7 Correct 54 ms 16732 KB Output is correct
8 Correct 55 ms 16720 KB Output is correct
9 Correct 56 ms 16712 KB Output is correct
10 Correct 49 ms 16736 KB Output is correct
11 Correct 51 ms 16580 KB Output is correct
12 Correct 50 ms 16736 KB Output is correct
13 Correct 63 ms 16740 KB Output is correct
14 Correct 727 ms 115796 KB Output is correct
15 Incorrect 58 ms 16712 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 3420 KB Output is correct
3 Correct 6 ms 3592 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -