oj.uz

Submission #1117184

# Submission time Handle Problem Language Result Execution time Memory
1117184 2024-11-22T21:34:45 Z PagodePaiva Strange Device (APIO19_strange_device) C++17
70 / 100
 5000 ms 485728 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94272 KB Output is correct
2 Correct 65 ms 95044 KB Output is correct
3 Correct 60 ms 95324 KB Output is correct
4 Correct 55 ms 94280 KB Output is correct
5 Correct 57 ms 94280 KB Output is correct
6 Correct 57 ms 94280 KB Output is correct
7 Correct 59 ms 94280 KB Output is correct
8 Correct 60 ms 94280 KB Output is correct
9 Correct 60 ms 94280 KB Output is correct
10 Correct 62 ms 94276 KB Output is correct
11 Correct 63 ms 94276 KB Output is correct
12 Correct 62 ms 94284 KB Output is correct
13 Correct 66 ms 94136 KB Output is correct
14 Correct 60 ms 94152 KB Output is correct
15 Correct 64 ms 94280 KB Output is correct
16 Correct 67 ms 95084 KB Output is correct
17 Correct 125 ms 102072 KB Output is correct
18 Correct 62 ms 94280 KB Output is correct

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 62 ms 94252 KB Output is correct
4 Correct 74 ms 94220 KB Output is correct
5 Correct 65 ms 94280 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94280 KB Output is correct
2 Correct 67 ms 94436 KB Output is correct
3 Correct 73 ms 94540 KB Output is correct
4 Correct 68 ms 94548 KB Output is correct
5 Correct 288 ms 134504 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94276 KB Output is correct
2 Correct 697 ms 211784 KB Output is correct
3 Correct 641 ms 204616 KB Output is correct
4 Correct 651 ms 204636 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94276 KB Output is correct
2 Correct 697 ms 211784 KB Output is correct
3 Correct 641 ms 204616 KB Output is correct
4 Correct 651 ms 204636 KB Output is correct
5 Correct 64 ms 94280 KB Output is correct
6 Correct 1821 ms 361360 KB Output is correct
7 Correct 687 ms 184956 KB Output is correct
8 Correct 1929 ms 361248 KB Output is correct
9 Correct 2063 ms 361840 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94276 KB Output is correct
2 Correct 697 ms 211784 KB Output is correct
3 Correct 641 ms 204616 KB Output is correct
4 Correct 651 ms 204636 KB Output is correct
5 Correct 65 ms 94280 KB Output is correct
6 Correct 151 ms 112060 KB Output is correct
7 Correct 213 ms 122808 KB Output is correct
8 Correct 208 ms 124392 KB Output is correct
9 Correct 208 ms 123032 KB Output is correct
10 Correct 160 ms 110764 KB Output is correct
11 Correct 222 ms 122808 KB Output is correct
12 Correct 207 ms 122968 KB Output is correct
13 Correct 224 ms 121284 KB Output is correct
14 Correct 163 ms 112280 KB Output is correct
15 Correct 229 ms 114144 KB Output is correct
16 Correct 221 ms 112576 KB Output is correct
17 Correct 400 ms 133332 KB Output is correct
18 Correct 2418 ms 382976 KB Output is correct
19 Correct 2692 ms 368268 KB Output is correct
20 Correct 2770 ms 368304 KB Output is correct
21 Correct 224 ms 121600 KB Output is correct
22 Correct 217 ms 121720 KB Output is correct
23 Correct 165 ms 112036 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 94376 KB Output is correct
2 Correct 176 ms 112316 KB Output is correct
3 Correct 222 ms 112564 KB Output is correct
4 Correct 4118 ms 321664 KB Output is correct
5 Correct 241 ms 113332 KB Output is correct
6 Correct 227 ms 113084 KB Output is correct
7 Correct 221 ms 113332 KB Output is correct
8 Correct 239 ms 114864 KB Output is correct
9 Correct 257 ms 114876 KB Output is correct
10 Correct 193 ms 112308 KB Output is correct
11 Correct 153 ms 112308 KB Output is correct
12 Correct 175 ms 112224 KB Output is correct
13 Correct 220 ms 113084 KB Output is correct
14 Correct 1678 ms 211836 KB Output is correct
15 Correct 167 ms 104884 KB Output is correct
16 Correct 1819 ms 274340 KB Output is correct
17 Correct 1018 ms 198460 KB Output is correct
18 Correct 71 ms 94320 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94272 KB Output is correct
2 Correct 65 ms 95044 KB Output is correct
3 Correct 60 ms 95324 KB Output is correct
4 Correct 55 ms 94280 KB Output is correct
5 Correct 57 ms 94280 KB Output is correct
6 Correct 57 ms 94280 KB Output is correct
7 Correct 59 ms 94280 KB Output is correct
8 Correct 60 ms 94280 KB Output is correct
9 Correct 60 ms 94280 KB Output is correct
10 Correct 62 ms 94276 KB Output is correct
11 Correct 63 ms 94276 KB Output is correct
12 Correct 62 ms 94284 KB Output is correct
13 Correct 66 ms 94136 KB Output is correct
14 Correct 60 ms 94152 KB Output is correct
15 Correct 64 ms 94280 KB Output is correct
16 Correct 67 ms 95084 KB Output is correct
17 Correct 125 ms 102072 KB Output is correct
18 Correct 62 ms 94280 KB Output is correct
19 Correct 61 ms 94280 KB Output is correct
20 Correct 66 ms 94280 KB Output is correct
21 Correct 62 ms 94252 KB Output is correct
22 Correct 74 ms 94220 KB Output is correct
23 Correct 65 ms 94280 KB Output is correct
24 Correct 62 ms 94280 KB Output is correct
25 Correct 67 ms 94436 KB Output is correct
26 Correct 73 ms 94540 KB Output is correct
27 Correct 68 ms 94548 KB Output is correct
28 Correct 288 ms 134504 KB Output is correct
29 Correct 67 ms 94276 KB Output is correct
30 Correct 697 ms 211784 KB Output is correct
31 Correct 641 ms 204616 KB Output is correct
32 Correct 651 ms 204636 KB Output is correct
33 Correct 64 ms 94280 KB Output is correct
34 Correct 1821 ms 361360 KB Output is correct
35 Correct 687 ms 184956 KB Output is correct
36 Correct 1929 ms 361248 KB Output is correct
37 Correct 2063 ms 361840 KB Output is correct
38 Correct 65 ms 94280 KB Output is correct
39 Correct 151 ms 112060 KB Output is correct
40 Correct 213 ms 122808 KB Output is correct
41 Correct 208 ms 124392 KB Output is correct
42 Correct 208 ms 123032 KB Output is correct
43 Correct 160 ms 110764 KB Output is correct
44 Correct 222 ms 122808 KB Output is correct
45 Correct 207 ms 122968 KB Output is correct
46 Correct 224 ms 121284 KB Output is correct
47 Correct 163 ms 112280 KB Output is correct
48 Correct 229 ms 114144 KB Output is correct
49 Correct 221 ms 112576 KB Output is correct
50 Correct 400 ms 133332 KB Output is correct
51 Correct 2418 ms 382976 KB Output is correct
52 Correct 2692 ms 368268 KB Output is correct
53 Correct 2770 ms 368304 KB Output is correct
54 Correct 224 ms 121600 KB Output is correct
55 Correct 217 ms 121720 KB Output is correct
56 Correct 165 ms 112036 KB Output is correct
57 Correct 58 ms 94376 KB Output is correct
58 Correct 176 ms 112316 KB Output is correct
59 Correct 222 ms 112564 KB Output is correct
60 Correct 4118 ms 321664 KB Output is correct
61 Correct 241 ms 113332 KB Output is correct
62 Correct 227 ms 113084 KB Output is correct
63 Correct 221 ms 113332 KB Output is correct
64 Correct 239 ms 114864 KB Output is correct
65 Correct 257 ms 114876 KB Output is correct
66 Correct 193 ms 112308 KB Output is correct
67 Correct 153 ms 112308 KB Output is correct
68 Correct 175 ms 112224 KB Output is correct
69 Correct 220 ms 113084 KB Output is correct
70 Correct 1678 ms 211836 KB Output is correct
71 Correct 167 ms 104884 KB Output is correct
72 Correct 1819 ms 274340 KB Output is correct
73 Correct 1018 ms 198460 KB Output is correct
74 Correct 71 ms 94320 KB Output is correct
75 Correct 68 ms 94280 KB Output is correct
76 Correct 68 ms 94228 KB Output is correct
77 Correct 74 ms 94164 KB Output is correct
78 Correct 67 ms 94280 KB Output is correct
79 Correct 74 ms 95824 KB Output is correct
80 Correct 1405 ms 176792 KB Output is correct
81 Correct 3928 ms 321764 KB Output is correct
82 Correct 3508 ms 388576 KB Output is correct
83 Execution timed out 5095 ms 485728 KB Time limit exceeded
84 Halted 0 ms 0 KB -