Submission #821852

#	Time	Username	Problem	Language	Result	Execution time	Memory
821852		7mody	Strange Device (APIO19_strange_device)	C++17	100 / 100	438 ms	56684 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

void solve(){
    ll n,a,b; cin >> n >> a >> b;
    vector<pair<ll,ll>> arr(n);
    ll curr=0;
    for(int i=0; i < n;i++){
        cin >> arr[i].first >> arr[i].second;
        curr+=arr[i].second - arr[i].first +1;
    }
    ll x=a/(__gcd(b+1,a));
    ll maxi=x*b;
    if((arr[n-1].second-1)< maxi){
        cout << curr << endl;
        return;
    }
    vector<pair<ll,ll>> ans;
    for(int i=0; i < n;i++){
        if(arr[i].second - arr[i].first +1>=maxi){
            cout << maxi << endl;
            return;
        }
        arr[i].second%=maxi;
        arr[i].first%=maxi;
        if(arr[i].first > arr[i].second){
            ans.push_back({arr[i].first,maxi-1ll});
            ans.push_back({0ll,arr[i].second});
        } else{
            ans.push_back({arr[i].first, arr[i].second});
        }
    }
    sort(ans.begin(),ans.end());
    vector<pair<ll,ll>> add;
    curr=-1;
    for(auto c: ans){
        if(curr==-1){
            curr=0;
            add.push_back(c);
        } else if(c.first > add[curr].second){
            add.push_back(c);
            curr++;
        } else{
            add[curr].second=max(add[curr].second,c.second);
        }
    }
    ll out=0;
    for(auto c : add) out += c.second - c.first +1;
    cout << out << endl;
}

int main(){
    ios::sync_with_stdio(false);cout.tie();cin.tie();
    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

strange_device.cpp: In function 'void solve()':
strange_device.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
    9 |     for(int i=0; i < n;i++){
      |                  ~~^~~
strange_device.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i < n;i++){
      |                  ~~^~~
strange_device.cpp:38:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if(curr==-1){
      |            ~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30