oj.uz

Submission #932930

# Submission time Handle Problem Language Result Execution time Memory
932930 2024-02-24T14:47:40 Z 12345678 Strange Device (APIO19_strange_device) C++17
35 / 100
 583 ms 78768 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 (tmp >= LLONG_MAX/b) 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;
}

/*
3 5 10
1 20
50 68
89 98

*/

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:36: warning: left operand of comma operator has no effect [-Wunused-value]
   26 |     if (tmp >= LLONG_MAX/b) 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 2392 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 1 ms 2484 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 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 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 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 3164 KB Output is correct
17 Correct 48 ms 12876 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 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 0 ms 2396 KB Output is correct
5 Incorrect 1 ms 2392 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 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 172 ms 16220 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Correct 489 ms 78708 KB Output is correct
3 Correct 501 ms 78672 KB Output is correct
4 Correct 544 ms 78704 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Correct 489 ms 78708 KB Output is correct
3 Correct 501 ms 78672 KB Output is correct
4 Correct 544 ms 78704 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 497 ms 78688 KB Output is correct
7 Correct 524 ms 78720 KB Output is correct
8 Correct 518 ms 78724 KB Output is correct
9 Correct 577 ms 78708 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2648 KB Output is correct
2 Correct 489 ms 78708 KB Output is correct
3 Correct 501 ms 78672 KB Output is correct
4 Correct 544 ms 78704 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 44 ms 12884 KB Output is correct
7 Correct 45 ms 12932 KB Output is correct
8 Correct 46 ms 12932 KB Output is correct
9 Correct 48 ms 12884 KB Output is correct
10 Correct 44 ms 12880 KB Output is correct
11 Correct 44 ms 13040 KB Output is correct
12 Correct 44 ms 12880 KB Output is correct
13 Correct 56 ms 12932 KB Output is correct
14 Correct 43 ms 12928 KB Output is correct
15 Correct 51 ms 12880 KB Output is correct
16 Correct 51 ms 12884 KB Output is correct
17 Correct 51 ms 13204 KB Output is correct
18 Correct 492 ms 78712 KB Output is correct
19 Correct 518 ms 78716 KB Output is correct
20 Correct 565 ms 78708 KB Output is correct
21 Correct 46 ms 12884 KB Output is correct
22 Correct 57 ms 13036 KB Output is correct
23 Correct 75 ms 10628 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 51 ms 12884 KB Output is correct
3 Correct 54 ms 13032 KB Output is correct
4 Correct 553 ms 78672 KB Output is correct
5 Correct 58 ms 12936 KB Output is correct
6 Correct 53 ms 12892 KB Output is correct
7 Correct 51 ms 12884 KB Output is correct
8 Correct 60 ms 12844 KB Output is correct
9 Correct 48 ms 12884 KB Output is correct
10 Correct 47 ms 12884 KB Output is correct
11 Correct 47 ms 12880 KB Output is correct
12 Correct 50 ms 12884 KB Output is correct
13 Correct 52 ms 12944 KB Output is correct
14 Correct 583 ms 78768 KB Output is correct
15 Correct 48 ms 12936 KB Output is correct
16 Correct 478 ms 78676 KB Output is correct
17 Correct 479 ms 78676 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 2392 KB Output is correct
2 Correct 6 ms 3164 KB Output is correct
3 Correct 5 ms 3164 KB Output is correct
4 Correct 1 ms 2484 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 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 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 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 3164 KB Output is correct
17 Correct 48 ms 12876 KB Output is correct
18 Incorrect 1 ms 2396 KB Output isn't correct
19 Halted 0 ms 0 KB -