oj.uz

Submission #932929

# Submission time Handle Problem Language Result Execution time Memory
932929 2024-02-24T14:46:11 Z 12345678 Strange Device (APIO19_strange_device) C++17
35 / 100
 662 ms 97620 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long

const int nx=1e6+5;
ll n, a, b, l[nx], r[nx], sm, p, mx, res, tmp;
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;
    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);
    tmp=a/__gcd(a, b+1);
    if ((double) tmp * (double) (b) >= LLONG_MAX) return sm, 0;
    p=tmp*b;
    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;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   24 |     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);
      |                   ~^~~
strange_device.cpp:26:58: warning: left operand of comma operator has no effect [-Wunused-value]
   26 |     if ((double) tmp * (double) (b) >= LLONG_MAX) return sm, 0;
      |                                                          ^~
strange_device.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   29 |     for (int i=1; i<=n; i++) add_range(l[i], r[i]);
      |                   ~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 3584 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2520 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2516 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 5 ms 3596 KB Output is correct
17 Correct 50 ms 14980 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 1 ms 2512 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 190 ms 28768 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 496 ms 97580 KB Output is correct
3 Correct 517 ms 97248 KB Output is correct
4 Correct 556 ms 97224 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 496 ms 97580 KB Output is correct
3 Correct 517 ms 97248 KB Output is correct
4 Correct 556 ms 97224 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 511 ms 97476 KB Output is correct
7 Correct 532 ms 97620 KB Output is correct
8 Correct 514 ms 97368 KB Output is correct
9 Correct 662 ms 97360 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 496 ms 97580 KB Output is correct
3 Correct 517 ms 97248 KB Output is correct
4 Correct 556 ms 97224 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 45 ms 14976 KB Output is correct
7 Correct 46 ms 15056 KB Output is correct
8 Correct 47 ms 14928 KB Output is correct
9 Correct 49 ms 14932 KB Output is correct
10 Correct 49 ms 15084 KB Output is correct
11 Correct 46 ms 14928 KB Output is correct
12 Correct 45 ms 15004 KB Output is correct
13 Correct 49 ms 14932 KB Output is correct
14 Correct 45 ms 14976 KB Output is correct
15 Correct 54 ms 15096 KB Output is correct
16 Correct 58 ms 14932 KB Output is correct
17 Correct 50 ms 14960 KB Output is correct
18 Correct 499 ms 97404 KB Output is correct
19 Correct 560 ms 97264 KB Output is correct
20 Correct 649 ms 79016 KB Output is correct
21 Correct 47 ms 12884 KB Output is correct
22 Correct 48 ms 12888 KB Output is correct
23 Correct 83 ms 10868 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 58 ms 12884 KB Output is correct
3 Correct 54 ms 12888 KB Output is correct
4 Correct 599 ms 78672 KB Output is correct
5 Correct 52 ms 13032 KB Output is correct
6 Correct 53 ms 12892 KB Output is correct
7 Correct 52 ms 12924 KB Output is correct
8 Correct 53 ms 13040 KB Output is correct
9 Correct 50 ms 13036 KB Output is correct
10 Correct 60 ms 13140 KB Output is correct
11 Correct 49 ms 12880 KB Output is correct
12 Correct 47 ms 12892 KB Output is correct
13 Correct 53 ms 12912 KB Output is correct
14 Correct 649 ms 78672 KB Output is correct
15 Correct 45 ms 12932 KB Output is correct
16 Correct 492 ms 78932 KB Output is correct
17 Correct 491 ms 78708 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 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 5 ms 3584 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2520 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2516 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 5 ms 3596 KB Output is correct
17 Correct 50 ms 14980 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Halted 0 ms 0 KB -