oj.uz

Submission #729961

# Submission time Handle Problem Language Result Execution time Memory
729961 2023-04-24T23:52:15 Z MtSaka Strange Device (APIO19_strange_device) C++17
30 / 100
 625 ms 68988 KB 
#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)a;++i)
#define rep3(i,a,b) for(ll i=a;i<(ll)b;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define lb(v,x) lower_bound(all(v),x);
#define ub(v,x) upper_bound(all(v),x);
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    ll a,b;cin>>a>>b;
    ll g=gcd(a,b+1);
    if((ld)(1e18)/(ld)b<(ld)a/(ld)g){
        ll ans=0;
        rep(i,n){
            ll l,r;cin>>l>>r;
            ans+=r-l+1;
        }
        cout<<ans<<endl;return 0;
    }
    vector<pair<ll,ll>>v;
    ll md=a/g*b;
    rep(i,n){
        ll l,r;cin>>l>>r;
        r++;
        if(r-l>=md){
            cout<<md<<endl;return 0;
        }
        l%=md,r%=md;
        if(l>r){
            v.emplace_back(l,1);
            v.emplace_back(md,-1);
            v.emplace_back(0,1);
            v.emplace_back(r,-1);
        }
        else{
            v.emplace_back(l,1);
            v.emplace_back(r,-1);
        }
    }
    sort(all(v));
    ll ans=0,cnt=1;
    rep(i,1,v.size()){
        if(cnt>0){
            ans+=v[i].first-v[i-1].first;
        }
        cnt+=v[i].second;
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 5 ms 1240 KB Output is correct
3 Correct 6 ms 1232 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 337 ms 56944 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 529 ms 68868 KB Output isn't correct
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 Incorrect 529 ms 68868 KB Output isn't correct
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 Incorrect 529 ms 68868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 53 ms 7288 KB Output is correct
3 Correct 68 ms 7316 KB Output is correct
4 Correct 625 ms 68984 KB Output is correct
5 Correct 56 ms 7220 KB Output is correct
6 Correct 54 ms 7200 KB Output is correct
7 Correct 55 ms 7276 KB Output is correct
8 Correct 58 ms 7264 KB Output is correct
9 Correct 57 ms 7256 KB Output is correct
10 Correct 55 ms 7192 KB Output is correct
11 Correct 53 ms 7380 KB Output is correct
12 Correct 50 ms 7236 KB Output is correct
13 Correct 60 ms 7228 KB Output is correct
14 Correct 610 ms 68964 KB Output is correct
15 Correct 70 ms 7256 KB Output is correct
16 Correct 481 ms 68988 KB Output is correct
17 Correct 496 ms 68960 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 5 ms 1240 KB Output is correct
3 Correct 6 ms 1232 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -