oj.uz

Submission #1117121

# Submission time Handle Problem Language Result Execution time Memory
1117121 2024-11-22T20:44:53 Z PagodePaiva Strange Device (APIO19_strange_device) C++17
0 / 100
 5000 ms 368160 KB 
#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){
        if(!aux.empty()){
            auto [a, b] = aux.back();
            if(b < l) aux.push_back({l, r});
            else{
                aux.pop_back();
                aux.push_back({a, 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+1)/B;
        if(l == 1 and r == 20){
            //cout << a << ' ' << b << '\n';
        }
        if(a < b){
            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});
    }
    set <int> novos;
    int st = 0;
    for(auto [pos, valor] : mapear){
        res += (pos-st)*add;
        st = pos;
        for(auto [x, tp] : opp[valor]){
            //cout << pos << ' ' << tp << ' ' << x << '\n';
            if(tp == 0){
                auto it = s.lower_bound(x);
                if(it != s.end()){
                    int p = *it;
                    if(m[p] >= x) continue;
                }
                if(cnt[x] == 0) add++;
                novos.insert(x);
                cnt[x]++;
                m[x] = x;
            }
            else{
                if(cnt[x] == 0) continue;
                cnt[x]--;
                if(cnt[x] == 0){
                    add--;
                    novos.erase(x);
                    m.erase(x);
                }
            }   
        }
        //cout << add << '\n';
    }
    cout << res << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94280 KB Output is correct
2 Correct 45 ms 95044 KB Output is correct
3 Correct 43 ms 95244 KB Output is correct
4 Incorrect 39 ms 94288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 94200 KB Output is correct
2 Correct 48 ms 94280 KB Output is correct
3 Correct 51 ms 94332 KB Output is correct
4 Incorrect 51 ms 94280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94280 KB Output is correct
2 Incorrect 56 ms 94544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94288 KB Output is correct
2 Incorrect 586 ms 212136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94288 KB Output is correct
2 Incorrect 586 ms 212136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 94288 KB Output is correct
2 Incorrect 586 ms 212136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94144 KB Output is correct
2 Correct 171 ms 112372 KB Output is correct
3 Correct 237 ms 112808 KB Output is correct
4 Execution timed out 5087 ms 368160 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94280 KB Output is correct
2 Correct 45 ms 95044 KB Output is correct
3 Correct 43 ms 95244 KB Output is correct
4 Incorrect 39 ms 94288 KB Output isn't correct
5 Halted 0 ms 0 KB -