Submission #537341

#	Time	Username	Problem	Language	Result	Execution time	Memory
537341		DJ035	Strange Device (APIO19_strange_device)	C++17	100 / 100	547 ms	69856 KiB

strange_device

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#define MEM 1111111
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
#define pf push_front
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz size()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 1e17+7;
const ll MOD = 998244353;
ll gcd(ll a, ll b){
    if(a%b) return gcd(b, a%b);
    return b;
}
ll t,n,m,a,b;
ll l[MEM], r[MEM];
signed main(){
    sanic; cin.tie(0);
    cin >> n >> a >> b;
    for(int i=0; i<n; i++)
        cin >> l[i] >> r[i];
    if((ll)(1e18)/a<b){
        ll ret=0;
        for(int i=0; i<n; i++) ret += r[i]-l[i]+1;
        cout << ret;
        return 0;
    }
    t = (a/gcd(a,b+1))*b;
    for(int i=0; i<n; i++) {
        if(r[i]-l[i]+1>=t){
            cout << t;
            return 0;
        }
    }
    vector<pi> v;
    for(int i=0; i<n; i++){
        if(l[i]%t<=r[i]%t) v.pb({l[i]%t,r[i]%t});
        else{
            v.pb({l[i]%t,t-1});
            v.pb({0,r[i]%t});
        }
    }
    sort(all(v));
    ll mn=v[0].x, mx=v[0].y;
    ll ans=0;
    for(int i=1; i<v.sz; i++){
        if(mx<v[i].x){
            ans += mx-mn+1;
            mn = v[i].x;
            mx = v[i].y;
        }
        mx = max(v[i].y,mx);
    }
    ans += mx-mn+1;
    cout << ans;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:54: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]
   54 |     for(int i=1; i<v.sz; i++){
      |                   ^

• 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