Submission #983287

#	Time	Username	Problem	Language	Result	Execution time	Memory
983287		vjudge1	Strange Device (APIO19_strange_device)	C++17	15 / 100	536 ms	190952 KiB

strange_device

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

ll n, A, B;
ll l[1000005], r[1000005], sum = 0;
set<pair<ll, ll>> st1, st;
deque<pair<ll, ll>> st2;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> A >> B;
    for(int i = 1; i <= n; i++){
      cin >> l[i] >> r[i];
      sum += (r[i] - l[i] + 1);
    }
    if(sum <= 1e6){
      for(int i = 1; i <= n; i++){
          for(ll j = l[i]; j <= r[i]; j++){
              ll x = (j + j / B) % A, y = (j % B);
              st.insert({x, y});
          }
      }
      cout << int(st.size()) << "\n";
      return 0;
    }
    if(n == 1){
        ll x = (l[1] + l[1] / B) % A; 
        if(l[1] + B <= r[1]){
            ll num = l[1] + B;
            ll y = (num + num / B) % A;
            if(x == y){
                cout << B << "\n";
                return 0;
            }
            ll d = abs(x - y);
            ll ans = gcd(d, A);
            ll rg = l[1] + ans * B - 1;
            cout << min(r[1], rg) - l[1] + 1 << "\n";
            return 0;
        }
        else{
            cout << r[1] - l[1] + 1 << "\n";
            return 0;
        }
    }
    ll lf[n + 2], rg[n + 2];
    for(int i = 1; i <= n; i++){
        lf[i] = l[i];
        rg[i] = min(r[i], l[i] + A - 1);
        st1.insert({l[i], i});
        // st2.insert({rg[i], i});
    }
    ll ans = 0, mx = 0, mn = 0;
    bool f = 0;
    while(!st1.empty()){
        if(!f){
            auto it = st1.begin();
            mn = it->first;
            mx = r[it->second];
            f = 1;
            st1.erase(st1.begin());
            continue;
        }
        else{
            if(st1.begin()->first <= mx){
                auto it = st1.begin();
                mx = max(r[it->second], mx);
                st1.erase(st1.begin());
                continue;
            }
            else{
                ll res = A;
                if(res % 2 == 1) res *= 2;
                if(mx - mn + 1 >= res / 2){
                    cout << res / 2;
                    return 0;
                }
                ll l1 = (2 * mn) % A;
                ll r1 = (2 * mx) % A;
                if(l1 > r1){
                    st2.push_back({l1, A - (A % 2)});
                    st2.push_back({0, r1});
                }
                else{
                    st2.push_back({l1, r1});
                }
                auto it = st1.begin();
                mn = it->first;
                mx = r[it->second];
                f = 1;
                st1.erase(st1.begin());
            }
        }
    }
    cout << 1 / 0;
    ll res = A;
    if(res % 2 == 1) res *= 2;
    if(mx - mn + 1 >= res / 2){
        cout << res / 2;
        return 0;
    }
    ll l1 = (2 * mn) % A;
    ll r1 = (2 * mx) % A;
    if(l1 > r1){
        st2.push_back({l1, A - (A % 2)});
        st2.push_back({0, r1});
    }
    else st2.push_back({l1, r1});
    sort(st2.begin(), st2.end());
    f = 0;
    mn = 0, mx = 0;
    ans = 0;
    while(!st2.empty()){
        if(!f){
            f = 1;
            mn = st2.front().first;
            mx = st2.front().second;
            st2.pop_front();
            continue;
        }
        else{
            if(st2.front().first <= mx){
                mx = max(mx, st2.front().second);
                st2.pop_front();
                continue;
            }
            else{
                ans = (mx - mn) / 2;
                mn = st2.front().first;
                mn = st2.front().first;
                mx = st2.front().second;
                st2.pop_front();
            }
        }
    }
    ans += (mx - mn) / 2;
    cout << ans;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:121:15: warning: division by zero [-Wdiv-by-zero]
  121 |     cout << 1 / 0;
      |             ~~^~~
strange_device.cpp:72:8: warning: variable 'lf' set but not used [-Wunused-but-set-variable]
   72 |     ll lf[n + 2], rg[n + 2];
      |        ^~
strange_device.cpp:72:19: warning: variable 'rg' set but not used [-Wunused-but-set-variable]
   72 |     ll lf[n + 2], rg[n + 2];
      |                   ^~

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