제출 #1117184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117184		PagodePaiva	Strange Device (APIO19_strange_device)	C++17	70 / 100	5095 ms	485728 KiB

strange_device

#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #define long long long long

using namespace std;

const long long N = 4000010;
long long res = 0;
long long n;
long long A, B;
vector <pair <long long, long long>> opp[N];

long long gdc(long long x, long long y){
    if(x < y) swap(x, y);
    return (y == 0 ? x : gdc(y, x%y));
}

void corrigir(vector <pair <long long, long long>> &v){
    vector <pair <long long, long long>> aux;
    for(auto [l, r] : v){
        if(r-l+1 >= A) {
            aux.push_back({0, A-1});
            continue;
        }
        l %= A;
        r %= A;
        if(l <= r) aux.push_back({l, r});
        else{
            aux.push_back({l, A-1});
            aux.push_back({0,r});
        }
    }
    v = aux;
    sort(v.begin(), v.end());
    aux.clear();
    for(auto [l, r] : v){
        //cout << l << ' ' << r << '\n';
        if(!aux.empty()){
            auto [a, b] = aux.back();
            if(b < l) aux.push_back({l, r});
            else{
                aux.pop_back();
                aux.push_back({a, max(b, r)});
            }
        }
        else{
            aux.push_back({l, r});
        }
    }
    v = aux;
    return;
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> A >> B;
    A = A/gdc(A, B+1);
    vector <pair <long long, long long>> queries;
    vector <array <long long, 3>> corners;
    for(int i = 1;i <= n;i++){
        long long l, r;
        cin >> l >> r;
        if(r-l+1 <= B and r%B >= l%B){
            long long d = r/B;
            corners.push_back({l%B, r%B, (d%A)});
            continue;
        }
        if(l%B != 0){
            long long d = (l+B-1)/B;
            corners.push_back({l%B, B-1, ((d-1)%A+A)%A});
        }
        long long a = (l+B-1)/B;
        long long b = r/B;
        if(r%B == B-1){
            queries.push_back({a, b});
            continue;
        }
        if(B*a <= B*b-1){
            queries.push_back({a, b-1});
        }
        if(r%B != B-1){
            corners.push_back({0, r%B, b%A});
        }
    }
    corrigir(queries);
    //set <long long> s;
    map <long long, long long> m;
    map <long long ,int> cnt;
    long long add = 0;
    //cout << "cte:\n";
    for(auto [l, r] : queries){
        //cout << l << ' ' << r << '\n';
        m[l] = r;
        add += r-l+1;
        //s.insert(l);
    }
    //cout << '\n';
    set <long long> valores;
    for(auto [l, r, w] : corners){
        //cout << l << ' ' << r << ' ' << w << '\n';
        valores.insert(l);
        valores.insert(r+1);
    }
    map <long long, int> mapear;
    int con = 0;
    for(auto x : valores){
        mapear[x] = con;
        con++;
    }
    mapear[B] = con;
    con++;
    for(auto [l, r, w] : corners){
        opp[mapear[l]].push_back({w, 0});
        opp[mapear[r+1]].push_back({w, 1});
    }
    long long st = 0;
    vector <pair <long long, long long>> v;
    for(auto [aa, bb] : m){
        v.push_back({aa, bb});
    }
    for(auto [pos, valor] : mapear){
        res += (pos-st)*add;
        st = pos;
        for(auto [x, tp] : opp[valor]){
            if(tp == 0){
                long long d = upper_bound(v.begin(), v.end(), make_pair(x, (long long)1e18+1))-v.begin();
                if(d != 0) {
                    d--;
                    if(v[d].second >= x) continue;
                }
                if(cnt[x] == 0) add++;
                cnt[x]++;
            }
            else{
                auto it = cnt.find(x);
                if(it == cnt.end()) continue;
                auto [_, d] = *it;
                if(d == 1){
                    cnt.erase(it);
                    add--;
                    continue;
                }
                cnt[x]--;
            }   
        }
        //cout << add << '\n';
    }
    cout << res << '\n';
    return 0;
}

/*
10 7 1
3 5
8 11
26 33
40 52
65 69
83 95
113 123
135 136
154 166
182 185
*/

• 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: 0 / 30