oj.uz

Submission #1117129

# Submission time Handle Problem Language Result Execution time Memory
1117129 2024-11-22T20:53:33 Z PagodePaiva Strange Device (APIO19_strange_device) C++17
15 / 100
 5000 ms 524288 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(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.upper_bound(x);
                if(it != s.begin()){
                    it--;
                    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 54 ms 94288 KB Output is correct
2 Correct 74 ms 95436 KB Output is correct
3 Correct 85 ms 95640 KB Output is correct
4 Correct 64 ms 94160 KB Output is correct
5 Correct 65 ms 94280 KB Output is correct
6 Correct 66 ms 94288 KB Output is correct
7 Correct 62 ms 94280 KB Output is correct
8 Correct 65 ms 94236 KB Output is correct
9 Incorrect 67 ms 94288 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94280 KB Output is correct
2 Correct 66 ms 94280 KB Output is correct
3 Correct 68 ms 94280 KB Output is correct
4 Correct 68 ms 94236 KB Output is correct
5 Correct 66 ms 94380 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94216 KB Output is correct
2 Correct 1308 ms 354660 KB Output is correct
3 Correct 802 ms 256604 KB Output is correct
4 Correct 799 ms 256600 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94216 KB Output is correct
2 Correct 1308 ms 354660 KB Output is correct
3 Correct 802 ms 256604 KB Output is correct
4 Correct 799 ms 256600 KB Output is correct
5 Correct 58 ms 94280 KB Output is correct
6 Correct 3766 ms 524288 KB Output is correct
7 Correct 1200 ms 246652 KB Output is correct
8 Correct 3801 ms 524288 KB Output is correct
9 Correct 3662 ms 524288 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94216 KB Output is correct
2 Correct 1308 ms 354660 KB Output is correct
3 Correct 802 ms 256604 KB Output is correct
4 Correct 799 ms 256600 KB Output is correct
5 Correct 61 ms 94280 KB Output is correct
6 Correct 219 ms 126656 KB Output is correct
7 Correct 365 ms 140728 KB Output is correct
8 Correct 398 ms 140728 KB Output is correct
9 Correct 367 ms 140728 KB Output is correct
10 Correct 264 ms 122548 KB Output is correct
11 Correct 425 ms 140820 KB Output is correct
12 Correct 369 ms 140780 KB Output is correct
13 Correct 362 ms 139192 KB Output is correct
14 Correct 177 ms 116132 KB Output is correct
15 Incorrect 453 ms 129184 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94280 KB Output is correct
2 Correct 203 ms 116024 KB Output is correct
3 Correct 259 ms 113076 KB Output is correct
4 Execution timed out 5083 ms 396040 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94288 KB Output is correct
2 Correct 74 ms 95436 KB Output is correct
3 Correct 85 ms 95640 KB Output is correct
4 Correct 64 ms 94160 KB Output is correct
5 Correct 65 ms 94280 KB Output is correct
6 Correct 66 ms 94288 KB Output is correct
7 Correct 62 ms 94280 KB Output is correct
8 Correct 65 ms 94236 KB Output is correct
9 Incorrect 67 ms 94288 KB Output isn't correct
10 Halted 0 ms 0 KB -