oj.uz

Submission #635813

# Submission time Handle Problem Language Result Execution time Memory
635813 2022-08-27T04:19:17 Z PoonYaPat Strange Device (APIO19_strange_device) C++14
0 / 100
 8 ms 2108 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll n,A,B,mod,ans;
set<pll> s; //(end,start)

void insert(pll a) {
    if (s.empty()) {
        s.insert(a);
        ans+=(a.second-a.first+1);
    } else {
        auto it1=s.upper_bound(pll(a.first,LLONG_MAX));
        auto it2=s.upper_bound(pll(a.second,LLONG_MAX));
        ll mmin, mmax;
        auto ed=it1,st=it1;

        if (it1==s.begin()) mmin=a.first;
        else {
            auto h=it1; --h;
            if ((*h).second>=a.first) mmin=(*h).first,st=h;
            else mmin=a.first,st=it1;
        }

        ed=it2;
        if (it2==s.begin()) mmax=a.second;
        else {
            --it2;
            mmax=max(a.second,(*it2).second);
        }

        for (auto k=st; k!=ed; ++k) {
            ans-=((*k).second-(*k).first+1);
            auto p=k; s.erase(p);
        }

        s.insert(pll(mmin,mmax));
        ans+=(mmax-mmin+1);

        //cout<<ans<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>A>>B;

    mod=(A*B)/__gcd(A,B+1);

    while (n--) {
        ll l,r;
        cin>>l>>r;
        if (r-l+1>=mod) {
            cout<<mod;
            return 0;
        }
        l%=mod;
        r%=mod;

        if (l<=r) insert(pll(l,r));
        else insert(pll(l,mod-1)), insert(pll(0,r));
    }

    cout<<ans;
}
/*
2 3 3
7 9
17 18
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Runtime error 1 ms 464 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 8 ms 2108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 8 ms 2108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 8 ms 2108 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -