제출 #260168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260168		pure_mem	Strange Device (APIO19_strange_device)	C++14	10 / 100	1008 ms	119544 KiB

strange_device

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 1e5 + 12;
const ll INF = 1e18;

ll gcd(ll x, ll y){ return (y == 0 ? x: gcd(y, x % y));}

int n;
ll A, B;
multiset<ll> st;
vector< pair< pair<ll, ll>, ll > > g;

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> n >> A >> B;
    ll period = gcd(A, B + 1);
    bool exc = 0;
    if(((INF + A - 1) / A + B - 1) / B < period){
    	exc = 1;
    }
    else{
    	period *= A * B;
    }
    ll res = 0;
    for(int i = 1;i <= n;i++){
    	ll l, r;
    	cin >> l >> r;
    	if(exc){
    		res += r - l + 1;
    		continue;
    	}
    	if(l + period - 1 <= r){
    		cout << period;
    		return 0;	
    	}
    	else{
    		l %= period, r %= period;
    		if(l <= r){
    			g.push_back(MP(MP(l, -1), r));
    			g.push_back(MP(MP(r, 1), l));
    		}
    		else{
    			g.push_back(MP(MP(l, -1), period - 1));
    			g.push_back(MP(MP(period - 1, 1), l));

    			g.push_back(MP(MP(0, -1), r));
    			g.push_back(MP(MP(r, 1), 0));
    		}
    	}
    }
    if(exc)
    	return cout << res, 0;
    sort(g.begin(), g.end());
    for(pair< pair<ll, ll>, ll> v: g){
    	if(v.X.Y < 0){
    		res += v.Y - v.X.X + 1;
    		if(!st.empty()){
    			ll z = *st.begin();
    			z *= -1;
    			res -= min(v.Y, z) - v.X.X + 1;
    		}
    		st.insert(-v.Y);
    	}
    	else{
    		st.erase(st.find(-v.X.X));
    	}
    }
    cout << res;
}

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