제출 #974657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
974657		Abito	이상한 기계 (APIO19_strange_device)	C++17	5 / 100	3276 ms	524288 KiB

strange_device

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=1e6+5;
int n,a,b,l[N],r[N];
pair<int,int> f(int x){
    return {(x+x/b)%a,x%b};
}
map<pair<int,int>,int> mp;
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>a>>b;
    for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
    vector<pair<int,int>> v;
    v.pb(f(0));mp[f(0)]=0;
    for (int i=1;;i++){
        if (mp.find(f(i))!=mp.end()) break;
        v.pb(f(i));
        mp[f(i)]=i;
    }int sz=v.size();//cout<<sz<<endl;
    vector<pair<int,int>> rng;
    for (int i=1;i<=n;i++){
        if (r[i]-l[i]+1>=sz) rng.pb({0,sz-1});
        int L=mp[f(l[i])],R=(L+r[i]-l[i]);
        if (R%sz>=L) rng.pb({L,R%sz});
        else{
            rng.pb({L,sz-1});
            rng.pb({0,R%sz});
        }
    }
    sort(rng.begin(),rng.end());
    set<pair<int,int>> s;
    pair<int,int> cur=rng[0];
    for (auto u:rng){
        int l=max(u.F,cur.F),r=min(u.S,cur.S);
        if (l>r){
            s.ep(cur);
            cur=u;
        }
        else{
            cur.F=min(cur.F,u.F);
            cur.S=max(cur.S,u.S);
        }
    }
    s.ep(cur);
    int ans=0;
    for (auto u:s) ans+=u.S-u.F+1;
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 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