Submission #1117154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117154		PagodePaiva	Strange Device (APIO19_strange_device)	C++17	70 / 100	5062 ms	457072 KiB

strange_device

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 4000010;
long long res = 0;
int n;
long long A, B;
vector <pair <int, int>> 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 <int, int>> &v){
    vector <pair <int, int>> 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 <int, int>> queries;
    vector <array <int, 3>> corners;
    for(int i = 1;i <= n;i++){
        int l, r;
        cin >> l >> r;
        if(r-l+1 <= B and r%B >= l%B){
            int d = r/B;
            corners.push_back({l%B, r%B, (d%A)});
            continue;
        }
        if(l%B != 0){
            int d = (l+B-1)/B;
            corners.push_back({l%B, B-1, ((d-1)%A+A)%A});
        }
        int a = (l+B-1)/B;
        int 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});
        }
    }
    set <pair <int, int>> intervalos;
    corrigir(queries);
    set <int> s;
    map <int, int> m;
    map <int ,int> cnt;
    int 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 <int> valores;
    for(auto [l, r, w] : corners){
        //cout << l << ' ' << r << ' ' << w << '\n';
        valores.insert(l);
        valores.insert(r+1);
    }
    map <int, 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});
    }
    int st = 0;
    for(auto [pos, valor] : mapear){
        res += (pos-st)*add;
        st = pos;
        for(auto [x, tp] : opp[valor]){
            if(tp == 0){
                auto it = s.upper_bound(x);
                if(it != s.begin()){
                    it--;
                    int p = *it;
                    if(m[p] >= x) continue;
                }
                if(cnt[x] == 0) add++;
                cnt[x]++;
            }
            else{
                if(cnt[x] == 0) continue;
                cnt[x]--;
                if(cnt[x] == 0){
                    add--;
                }
            }   
        }
        //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