Submission #835368

#	Time	Username	Problem	Language	Result	Execution time	Memory
835368		dimashhh	Strange Device (APIO19_strange_device)	C++17	100 / 100	386 ms	69752 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 1,MOD = 1e9 + 7;

ll n,l[N],r[N],a,b,ans;
__int128_t A,B,cyc,inf;
vector<pair<ll,ll>> all;
void test(){
    cin >> n >> a >> b;
    A = a;
    B = b;
    for(int i = 1;i <= n;i++){
        cin >> l[i] >> r[i];
    }
    if(n == 1){
          ll x = a / gcd(a,b + 1),val = r[1] - l[1] + 1;
          if(x >= (val + b - 1) / val){
              cout << (x % MOD * (b % MOD)) % MOD;
              return;
          }
          cout << val % MOD;
          return;
      }
    cyc = A * B / (gcd(a,b + 1));
    inf = r[n];
    
    ll _ = a * b / (gcd(a,b + 1));
    for(int i = 1;i <= n;i++){
        l[i] %= _;
        r[i] %= _;
        // cout << l[i] << ' ' << r[i] << '\n';
        if(r[i] >= l[i]){
            all.push_back({l[i],r[i]});
            continue;
        }
        all.push_back({0,r[i]});
        all.push_back({l[i],_ - 1});
    }
    ll ans = 0;
    sort(all.begin(),all.end());
    // for(auto [x,y]:all){
    //     cout << x << ' ' << y << '\n';
    // }
    // cout << '\n';
    for(int i = 0;i < all.size();i++){
        ll mx = all[i].second,_l = all[i].first;
        for(int j = i + 1;j < all.size();j++){
            if(mx >= all[j].first){
                i = j;
                mx = max(mx,all[j].second);
            }else break;
        }
        // cout << _l << ' ' << mx << ' ' << i << '\n';
        ans += (mx - _l + 1) ;
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) test();
}

Compilation message (stderr)

strange_device.cpp: In function 'void test()':
strange_device.cpp:48:21: 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]
   48 |     for(int i = 0;i < all.size();i++){
      |                   ~~^~~~~~~~~~~~
strange_device.cpp:50:29: 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]
   50 |         for(int j = i + 1;j < all.size();j++){
      |                           ~~^~~~~~~~~~~~

• 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