oj.uz

Submission #635699

# Submission time Handle Problem Language Result Execution time Memory
635699 2022-08-26T17:19:31 Z PoonYaPat Strange Device (APIO19_strange_device) C++14
10 / 100
 918 ms 100436 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

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

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);
            //if (cnt==2) cout<<(*k).first<<" "<<(*k).second<<"\n";
            //cout<<(*p).first<<" "<<(*p).second<<"\n";
            //auto p=k; s.erase(p);
        }

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

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 0 ms 212 KB Output is correct
2 Correct 7 ms 1228 KB Output is correct
3 Correct 7 ms 1236 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Incorrect 1 ms 212 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 Incorrect 1 ms 340 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 324 KB Output is correct
2 Correct 766 ms 100052 KB Output is correct
3 Correct 798 ms 100032 KB Output is correct
4 Correct 918 ms 100104 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 766 ms 100052 KB Output is correct
3 Correct 798 ms 100032 KB Output is correct
4 Correct 918 ms 100104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 787 ms 100120 KB Output is correct
7 Correct 845 ms 100336 KB Output is correct
8 Correct 818 ms 100436 KB Output is correct
9 Correct 887 ms 100088 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 766 ms 100052 KB Output is correct
3 Correct 798 ms 100032 KB Output is correct
4 Correct 918 ms 100104 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 61 ms 10260 KB Output is correct
7 Incorrect 62 ms 10268 KB Output isn't correct
8 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 Correct 79 ms 10156 KB Output is correct
3 Correct 79 ms 10240 KB Output is correct
4 Correct 825 ms 100112 KB Output is correct
5 Correct 76 ms 10188 KB Output is correct
6 Correct 78 ms 10232 KB Output is correct
7 Correct 79 ms 10188 KB Output is correct
8 Correct 73 ms 10176 KB Output is correct
9 Correct 81 ms 10252 KB Output is correct
10 Correct 71 ms 10244 KB Output is correct
11 Correct 75 ms 10188 KB Output is correct
12 Correct 74 ms 10232 KB Output is correct
13 Correct 77 ms 10204 KB Output is correct
14 Correct 885 ms 100096 KB Output is correct
15 Incorrect 62 ms 9600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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