oj.uz

Submission #781548

# Submission time Handle Problem Language Result Execution time Memory
781548 2023-07-13T07:51:22 Z andecaandeci Strange Device (APIO19_strange_device) C++17
0 / 100
 517 ms 119144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
ll l[1000005],r[1000005];
ll gcd(ll a, ll b){
    if (b==0) return a;
    return gcd(b,a%b);
}
ll lcm (ll a, ll b){
    return a/gcd(a,b)*b;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>a>>b;
    ll t;
    ll x;
    if ((b+1)%a==0){
        t=b;
    }
    else{
        t=a*b;
    }
    // cout<<t;
    t=lcm(t,b);
    set <pair<ll,ll>> st;
    for (int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        ll u=r[i]-l[i]+1;
        if (u>=t){
            r[i]=1;
            l[i]=t;
        }
        else{
            ll q=r[i]-l[i];
            ll p=l[i]%t;
            l[i]=p;
            r[i]=l[i]+q;
        }
        st.insert({l[i],r[i]});
        // cout<<l[i]<<" "<<r[i]<<endl;
    }
    vector <pair<ll,ll>> pasang;
    for (auto z:st){
        pasang.push_back(z);
        // cout<<z.first<<" "<<z.second<<endl;
    }
    // sort(pasang+1,pasang+n+1);
    vector <pair<ll,ll>> jawab;
    ll last=pasang[0].second,previous=pasang[0].first;
    pasang.push_back({(ll)1e18+100,(ll)1e18+100});
    for (int i=1;i<=n;i++){
        if (pasang[i].first<last){
            last=pasang[i].second;
        }
        else{
            jawab.push_back({previous,last});
            previous=pasang[i].first;
            last=pasang[i].second;
        }
    }
    // if (previous>jawab[jawab.size()-1].second){
    //     // jawab.push_back({previous,last});
    // }
    ll ans=0;
    for (int i=0;i<jawab.size();i++){
        ans+=jawab[i].second-jawab[i].first+1;
    }
    cout<<ans;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<jawab.size();i++){
      |                  ~^~~~~~~~~~~~~
strange_device.cpp:17:8: warning: unused variable 'x' [-Wunused-variable]
   17 |     ll x;
      |        ^

Subtask #1
0 / 10.0

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

Subtask #3
0 / 5.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 50 ms 15260 KB Output is correct
3 Correct 46 ms 14468 KB Output is correct
4 Correct 486 ms 119064 KB Output is correct
5 Correct 51 ms 14436 KB Output is correct
6 Correct 47 ms 14396 KB Output is correct
7 Correct 50 ms 14460 KB Output is correct
8 Correct 49 ms 14532 KB Output is correct
9 Correct 60 ms 14452 KB Output is correct
10 Correct 45 ms 14448 KB Output is correct
11 Correct 45 ms 14380 KB Output is correct
12 Correct 45 ms 14368 KB Output is correct
13 Correct 48 ms 14380 KB Output is correct
14 Incorrect 498 ms 119144 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 340 KB Output is correct
2 Incorrect 5 ms 2000 KB Output isn't correct
3 Halted 0 ms 0 KB -