Submission #953878

#	Time	Username	Problem	Language	Result	Execution time	Memory
953878		Vladth11	Strange Device (APIO19_strange_device)	C++14	100 / 100	543 ms	70368 KiB

strange_device

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

const ll VALMAX = 2e18;

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll a, b;
    cin >> n >> a >> b;
    ll period;
    ll g = __gcd(a, b + 1);
    a /= g;
    if(a >= VALMAX / b){
        period = VALMAX;
    }else{
        period = a * b;
    }
    vector <pii> events;
    while(n--){
        ll l, r;
        cin >> l >> r;
        if(r - l + 1 >= period){
            events.push_back({0, 1});
            events.push_back({period, -1});
            continue;
        }
        l %= period;
        r %= period;
        if(l <= r){
            events.push_back({l, 1});
            events.push_back({r + 1, -1});
        }else{
            events.push_back({0, 1});
            events.push_back({r + 1, -1});
            events.push_back({l, 1});
            events.push_back({period, -1});
        }
    }
    int s = 0;
    ll total = 0;
    sort(events.begin(), events.end());
    for(int i = 0; i < events.size(); i++){
        s += events[i].second;
        if(events[i].first < period && (i < (events.size() - 1))){
            if(s > 0)
                total += (min(period, events[i + 1].first) - events[i].first);
        }
    }
    cout << total;
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:61:22: 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]
   61 |     for(int i = 0; i < events.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
strange_device.cpp:63:43: 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]
   63 |         if(events[i].first < period && (i < (events.size() - 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