oj.uz

Submission #932927

# Submission time Handle Problem Language Result Execution time Memory
932927 2024-02-24T14:43:40 Z 12345678 Strange Device (APIO19_strange_device) C++17
35 / 100
 674 ms 116052 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) > r[n]) 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:52: warning: left operand of comma operator has no effect [-Wunused-value]
   26 |     if ((double) tmp * (double) (b) > r[n]) 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 3588 KB Output is correct
3 Correct 5 ms 3416 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 2392 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 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2480 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 6 ms 3404 KB Output is correct
17 Correct 52 ms 16744 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 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 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 2 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2528 KB Output is correct
5 Correct 195 ms 41072 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 530 ms 115816 KB Output is correct
3 Correct 560 ms 115608 KB Output is correct
4 Correct 618 ms 115588 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 530 ms 115816 KB Output is correct
3 Correct 560 ms 115608 KB Output is correct
4 Correct 618 ms 115588 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 557 ms 115676 KB Output is correct
7 Correct 598 ms 115660 KB Output is correct
8 Correct 563 ms 115824 KB Output is correct
9 Correct 674 ms 115788 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 530 ms 115816 KB Output is correct
3 Correct 560 ms 115608 KB Output is correct
4 Correct 618 ms 115588 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 49 ms 16608 KB Output is correct
7 Correct 51 ms 16748 KB Output is correct
8 Correct 47 ms 16620 KB Output is correct
9 Correct 55 ms 16724 KB Output is correct
10 Correct 45 ms 16644 KB Output is correct
11 Correct 47 ms 16620 KB Output is correct
12 Correct 47 ms 16748 KB Output is correct
13 Correct 50 ms 16748 KB Output is correct
14 Correct 49 ms 16624 KB Output is correct
15 Correct 54 ms 16600 KB Output is correct
16 Correct 56 ms 16720 KB Output is correct
17 Correct 48 ms 16720 KB Output is correct
18 Correct 526 ms 115888 KB Output is correct
19 Correct 594 ms 116052 KB Output is correct
20 Correct 654 ms 115796 KB Output is correct
21 Correct 52 ms 16724 KB Output is correct
22 Correct 61 ms 16620 KB Output is correct
23 Correct 80 ms 23280 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 55 ms 16652 KB Output is correct
3 Correct 60 ms 16720 KB Output is correct
4 Correct 567 ms 115832 KB Output is correct
5 Correct 68 ms 16512 KB Output is correct
6 Correct 56 ms 16728 KB Output is correct
7 Correct 54 ms 16724 KB Output is correct
8 Correct 53 ms 16644 KB Output is correct
9 Correct 51 ms 16612 KB Output is correct
10 Correct 54 ms 16756 KB Output is correct
11 Correct 50 ms 16508 KB Output is correct
12 Correct 54 ms 16992 KB Output is correct
13 Correct 54 ms 16720 KB Output is correct
14 Correct 611 ms 115684 KB Output is correct
15 Correct 51 ms 16852 KB Output is correct
16 Correct 526 ms 115828 KB Output is correct
17 Correct 506 ms 115644 KB Output is correct
18 Incorrect 1 ms 2392 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 3588 KB Output is correct
3 Correct 5 ms 3416 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 2392 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 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2480 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 6 ms 3404 KB Output is correct
17 Correct 52 ms 16744 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Halted 0 ms 0 KB -