oj.uz

Submission #250109

# Submission time Handle Problem Language Result Execution time Memory
250109 2020-07-17T03:30:06 Z jeqcho Strange Device (APIO19_strange_device) C++17
20 / 100
 5000 ms 524292 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 1

int n;
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);
}

ll x(ll t)
{
    return (t + t/B) % A;
}

ll y(ll t)
{
    return t % B;
}

void ansB()
{
    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;
        }
        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;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>A>>B;
    if(B<=3)
    {
        ansB();
        return 0;
    }
    set<pii> ans;
    ll l,r;
    while(n--)
    {
        cin>>l>>r;
        for(ll t=l;t < r+1; ++t)
        {
            ans.insert({x(t),y(t)});
        }
    }
    cout<<sz(ans)<<endl;
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 46 ms 9336 KB Output is correct
3 Correct 65 ms 13964 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 43 ms 5368 KB Output is correct
16 Correct 29 ms 5504 KB Output is correct
17 Correct 74 ms 8824 KB Output is correct
18 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 3482 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 129 ms 24312 KB Output is correct
3 Correct 156 ms 24184 KB Output is correct
4 Correct 117 ms 23036 KB Output is correct
5 Execution timed out 5050 ms 46948 KB Time limit exceeded

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 552 ms 20052 KB Output is correct
3 Correct 537 ms 20564 KB Output is correct
4 Correct 539 ms 20564 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 552 ms 20052 KB Output is correct
3 Correct 537 ms 20564 KB Output is correct
4 Correct 539 ms 20564 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 549 ms 20568 KB Output is correct
7 Correct 545 ms 20568 KB Output is correct
8 Correct 523 ms 20564 KB Output is correct
9 Correct 562 ms 20564 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 552 ms 20052 KB Output is correct
3 Correct 537 ms 20564 KB Output is correct
4 Correct 539 ms 20564 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 220 ms 49912 KB Output is correct
7 Runtime error 2394 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 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 Runtime error 1761 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 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 Correct 46 ms 9336 KB Output is correct
3 Correct 65 ms 13964 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 43 ms 5368 KB Output is correct
16 Correct 29 ms 5504 KB Output is correct
17 Correct 74 ms 8824 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Runtime error 3482 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -