oj.uz

Submission #931926

# Submission time Handle Problem Language Result Execution time Memory
931926 2024-02-22T14:45:40 Z 12345678 Strange Device (APIO19_strange_device) C++17
10 / 100
 643 ms 78928 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 [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 2396 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 5 ms 3160 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 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 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 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 180 ms 16004 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 554 ms 78928 KB Output is correct
3 Incorrect 564 ms 78676 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 554 ms 78928 KB Output is correct
3 Incorrect 564 ms 78676 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 554 ms 78928 KB Output is correct
3 Incorrect 564 ms 78676 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 53 ms 13088 KB Output is correct
3 Correct 58 ms 12804 KB Output is correct
4 Correct 604 ms 78676 KB Output is correct
5 Correct 53 ms 12856 KB Output is correct
6 Correct 54 ms 12928 KB Output is correct
7 Correct 52 ms 12880 KB Output is correct
8 Correct 52 ms 12944 KB Output is correct
9 Correct 50 ms 12884 KB Output is correct
10 Correct 48 ms 12888 KB Output is correct
11 Correct 49 ms 12884 KB Output is correct
12 Correct 48 ms 12880 KB Output is correct
13 Correct 55 ms 12920 KB Output is correct
14 Correct 643 ms 78504 KB Output is correct
15 Incorrect 52 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 2396 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 5 ms 3160 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -