oj.uz

Submission #250108

# Submission time Handle Problem Language Result Execution time Memory
250108 2020-07-17T03:24:51 Z jeqcho Strange Device (APIO19_strange_device) C++17
10 / 100
 597 ms 23848 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

// solved subtask 4 and 5

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 >= maxlen)
        {
            FOR(j,i+1,n)cin>>l>>r;
            cout<<maxlen<<endl;
            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:76:24: warning: 'rdex' may be used uninitialized in this function [-Wmaybe-uninitialized]
             ans += rdex-ldex+1;
                    ~~~~^~~~~
strange_device.cpp:76: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 1 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 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 1 ms 384 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 1 ms 384 KB Output is correct
2 Correct 553 ms 23516 KB Output is correct
3 Correct 597 ms 22344 KB Output is correct
4 Correct 503 ms 22672 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 553 ms 23516 KB Output is correct
3 Correct 597 ms 22344 KB Output is correct
4 Correct 503 ms 22672 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 507 ms 22612 KB Output is correct
7 Correct 518 ms 22612 KB Output is correct
8 Correct 502 ms 22612 KB Output is correct
9 Correct 548 ms 22868 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 553 ms 23516 KB Output is correct
3 Correct 597 ms 22344 KB Output is correct
4 Correct 503 ms 22672 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 53 ms 5748 KB Output is correct
7 Correct 55 ms 5732 KB Output is correct
8 Correct 54 ms 5784 KB Output is correct
9 Correct 50 ms 5740 KB Output is correct
10 Correct 51 ms 5864 KB Output is correct
11 Correct 56 ms 5736 KB Output is correct
12 Correct 51 ms 5740 KB Output is correct
13 Correct 52 ms 5740 KB Output is correct
14 Correct 54 ms 5740 KB Output is correct
15 Incorrect 57 ms 5740 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 56 ms 5696 KB Output is correct
3 Correct 57 ms 5720 KB Output is correct
4 Correct 586 ms 23848 KB Output is correct
5 Correct 55 ms 5736 KB Output is correct
6 Correct 60 ms 5740 KB Output is correct
7 Correct 54 ms 5736 KB Output is correct
8 Correct 60 ms 5740 KB Output is correct
9 Correct 55 ms 5740 KB Output is correct
10 Correct 54 ms 5740 KB Output is correct
11 Correct 54 ms 5728 KB Output is correct
12 Correct 50 ms 5864 KB Output is correct
13 Correct 56 ms 5740 KB Output is correct
14 Incorrect 543 ms 23764 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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