oj.uz

Submission #249969

# Submission time Handle Problem Language Result Execution time Memory
249969 2020-07-16T15:56:24 Z jeqcho Strange Device (APIO19_strange_device) C++17
10 / 100
 562 ms 26512 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

ll A,B;

ll gcd(ll a, ll b)
{
    // O((log n)^2)
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    return (a * b) / gcd(a, b);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n>>A>>B;
    ll l,r;
    ll lcm1 = lcm(B+1,A);
    ll q = lcm1 / (B+1);
    ll maxlen = q*B;
    vector<pair<ll,ll>> segments;
    F0R(i,n)
    {
        cin>>l>>r;
        if(r-l+1 >= maxlen)
        {
            cout<<maxlen<<'\n';
            return 0;
        }
        l %= maxlen;
        r %= maxlen;
        if(r<l)
        {
            segments.pb({0,r});
            segments.pb({l,maxlen-1});
        }
        else segments.pb({l,r});
    }
    sort(all(segments));
    bool init=0;
    ll ldex,rdex;
    ll ans=0;
    pair<ll,ll> seg;
    F0R(i,sz(segments)+1)
    {
        if(i==sz(segments))
        {
            ans += rdex-ldex+1;
            break;
        }
        seg = segments[i];
        if(!init)
        {
            ldex=seg.f;
            rdex=seg.s;
            init=1;
        }
        else if(seg.f==ldex)
        {
            rdex = seg.s;
        }
        else
        {
            // seg.f > ldex
            if(seg.f <= rdex)
            {
                rdex = seg.s;
            }
            else
            {
                ans += rdex-ldex+1;
                ldex=seg.f;
                rdex=seg.s;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:73:24: warning: 'rdex' may be used uninitialized in this function [-Wmaybe-uninitialized]
             ans += rdex-ldex+1;
                    ~~~~^~~~~
strange_device.cpp:73:24: warning: 'ldex' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 6 ms 1152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 0 ms 384 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 520 ms 17008 KB Output is correct
3 Correct 509 ms 25240 KB Output is correct
4 Correct 504 ms 26440 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 520 ms 17008 KB Output is correct
3 Correct 509 ms 25240 KB Output is correct
4 Correct 504 ms 26440 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 547 ms 26452 KB Output is correct
7 Correct 533 ms 26372 KB Output is correct
8 Correct 523 ms 26324 KB Output is correct
9 Correct 562 ms 26512 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 520 ms 17008 KB Output is correct
3 Correct 509 ms 25240 KB Output is correct
4 Correct 504 ms 26440 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 50 ms 5724 KB Output is correct
7 Correct 66 ms 5736 KB Output is correct
8 Correct 64 ms 5740 KB Output is correct
9 Correct 50 ms 5736 KB Output is correct
10 Correct 52 ms 5736 KB Output is correct
11 Correct 53 ms 5740 KB Output is correct
12 Correct 49 ms 5736 KB Output is correct
13 Correct 55 ms 5740 KB Output is correct
14 Correct 52 ms 5740 KB Output is correct
15 Incorrect 54 ms 5748 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 53 ms 3948 KB Output is correct
3 Correct 54 ms 4716 KB Output is correct
4 Correct 555 ms 25172 KB Output is correct
5 Correct 57 ms 4844 KB Output is correct
6 Correct 55 ms 4716 KB Output is correct
7 Correct 53 ms 4716 KB Output is correct
8 Correct 57 ms 4712 KB Output is correct
9 Correct 55 ms 4712 KB Output is correct
10 Correct 57 ms 4732 KB Output is correct
11 Correct 52 ms 4712 KB Output is correct
12 Correct 55 ms 4880 KB Output is correct
13 Correct 56 ms 4716 KB Output is correct
14 Incorrect 555 ms 25280 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 6 ms 1152 KB Output isn't correct
3 Halted 0 ms 0 KB -