oj.uz

Submission #1117180

# Submission time Handle Problem Language Result Execution time Memory
1117180 2024-11-22T21:31:41 Z PagodePaiva Strange Device (APIO19_strange_device) C++17
70 / 100
 5000 ms 480364 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(long long 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 <long long> v;
    for(auto [aa, bb] : m){
        v.push_back(aa);
    }
    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(), x)-v.begin();
                if(d != 0) {
                    d--;
                    if(m[v[d]] >= 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 64 ms 94280 KB Output is correct
2 Correct 70 ms 95276 KB Output is correct
3 Correct 69 ms 95300 KB Output is correct
4 Correct 74 ms 94280 KB Output is correct
5 Correct 63 ms 94216 KB Output is correct
6 Correct 64 ms 94276 KB Output is correct
7 Correct 60 ms 94288 KB Output is correct
8 Correct 70 ms 94332 KB Output is correct
9 Correct 78 ms 94280 KB Output is correct
10 Correct 74 ms 94276 KB Output is correct
11 Correct 67 ms 94336 KB Output is correct
12 Correct 72 ms 94388 KB Output is correct
13 Correct 69 ms 94248 KB Output is correct
14 Correct 73 ms 94172 KB Output is correct
15 Correct 66 ms 94284 KB Output is correct
16 Correct 72 ms 95188 KB Output is correct
17 Correct 127 ms 102072 KB Output is correct
18 Correct 76 ms 94176 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 94344 KB Output is correct
2 Correct 77 ms 94280 KB Output is correct
3 Correct 82 ms 94280 KB Output is correct
4 Correct 70 ms 94280 KB Output is correct
5 Correct 82 ms 94196 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 94280 KB Output is correct
2 Correct 80 ms 94540 KB Output is correct
3 Correct 85 ms 94488 KB Output is correct
4 Correct 75 ms 94548 KB Output is correct
5 Correct 284 ms 134548 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 94280 KB Output is correct
2 Correct 730 ms 211864 KB Output is correct
3 Correct 621 ms 189292 KB Output is correct
4 Correct 623 ms 188612 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 94280 KB Output is correct
2 Correct 730 ms 211864 KB Output is correct
3 Correct 621 ms 189292 KB Output is correct
4 Correct 623 ms 188612 KB Output is correct
5 Correct 59 ms 94276 KB Output is correct
6 Correct 2083 ms 353600 KB Output is correct
7 Correct 669 ms 184968 KB Output is correct
8 Correct 2045 ms 353696 KB Output is correct
9 Correct 2171 ms 353732 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 94280 KB Output is correct
2 Correct 730 ms 211864 KB Output is correct
3 Correct 621 ms 189292 KB Output is correct
4 Correct 623 ms 188612 KB Output is correct
5 Correct 58 ms 94280 KB Output is correct
6 Correct 144 ms 112044 KB Output is correct
7 Correct 216 ms 122432 KB Output is correct
8 Correct 217 ms 122296 KB Output is correct
9 Correct 226 ms 122312 KB Output is correct
10 Correct 167 ms 110872 KB Output is correct
11 Correct 263 ms 122040 KB Output is correct
12 Correct 244 ms 122304 KB Output is correct
13 Correct 229 ms 120912 KB Output is correct
14 Correct 163 ms 112412 KB Output is correct
15 Correct 265 ms 114308 KB Output is correct
16 Correct 230 ms 112576 KB Output is correct
17 Correct 496 ms 132588 KB Output is correct
18 Correct 3860 ms 375548 KB Output is correct
19 Correct 3738 ms 361176 KB Output is correct
20 Correct 3733 ms 361088 KB Output is correct
21 Correct 263 ms 121228 KB Output is correct
22 Correct 231 ms 121180 KB Output is correct
23 Correct 155 ms 112048 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94284 KB Output is correct
2 Correct 181 ms 112248 KB Output is correct
3 Correct 235 ms 112568 KB Output is correct
4 Correct 4113 ms 324964 KB Output is correct
5 Correct 240 ms 113444 KB Output is correct
6 Correct 236 ms 113200 KB Output is correct
7 Correct 221 ms 113332 KB Output is correct
8 Correct 254 ms 114912 KB Output is correct
9 Correct 247 ms 114868 KB Output is correct
10 Correct 183 ms 112564 KB Output is correct
11 Correct 154 ms 112308 KB Output is correct
12 Correct 169 ms 113332 KB Output is correct
13 Correct 223 ms 113080 KB Output is correct
14 Correct 1536 ms 212520 KB Output is correct
15 Correct 168 ms 105140 KB Output is correct
16 Correct 1887 ms 276556 KB Output is correct
17 Correct 1022 ms 200988 KB Output is correct
18 Correct 66 ms 94280 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94280 KB Output is correct
2 Correct 70 ms 95276 KB Output is correct
3 Correct 69 ms 95300 KB Output is correct
4 Correct 74 ms 94280 KB Output is correct
5 Correct 63 ms 94216 KB Output is correct
6 Correct 64 ms 94276 KB Output is correct
7 Correct 60 ms 94288 KB Output is correct
8 Correct 70 ms 94332 KB Output is correct
9 Correct 78 ms 94280 KB Output is correct
10 Correct 74 ms 94276 KB Output is correct
11 Correct 67 ms 94336 KB Output is correct
12 Correct 72 ms 94388 KB Output is correct
13 Correct 69 ms 94248 KB Output is correct
14 Correct 73 ms 94172 KB Output is correct
15 Correct 66 ms 94284 KB Output is correct
16 Correct 72 ms 95188 KB Output is correct
17 Correct 127 ms 102072 KB Output is correct
18 Correct 76 ms 94176 KB Output is correct
19 Correct 77 ms 94344 KB Output is correct
20 Correct 77 ms 94280 KB Output is correct
21 Correct 82 ms 94280 KB Output is correct
22 Correct 70 ms 94280 KB Output is correct
23 Correct 82 ms 94196 KB Output is correct
24 Correct 70 ms 94280 KB Output is correct
25 Correct 80 ms 94540 KB Output is correct
26 Correct 85 ms 94488 KB Output is correct
27 Correct 75 ms 94548 KB Output is correct
28 Correct 284 ms 134548 KB Output is correct
29 Correct 72 ms 94280 KB Output is correct
30 Correct 730 ms 211864 KB Output is correct
31 Correct 621 ms 189292 KB Output is correct
32 Correct 623 ms 188612 KB Output is correct
33 Correct 59 ms 94276 KB Output is correct
34 Correct 2083 ms 353600 KB Output is correct
35 Correct 669 ms 184968 KB Output is correct
36 Correct 2045 ms 353696 KB Output is correct
37 Correct 2171 ms 353732 KB Output is correct
38 Correct 58 ms 94280 KB Output is correct
39 Correct 144 ms 112044 KB Output is correct
40 Correct 216 ms 122432 KB Output is correct
41 Correct 217 ms 122296 KB Output is correct
42 Correct 226 ms 122312 KB Output is correct
43 Correct 167 ms 110872 KB Output is correct
44 Correct 263 ms 122040 KB Output is correct
45 Correct 244 ms 122304 KB Output is correct
46 Correct 229 ms 120912 KB Output is correct
47 Correct 163 ms 112412 KB Output is correct
48 Correct 265 ms 114308 KB Output is correct
49 Correct 230 ms 112576 KB Output is correct
50 Correct 496 ms 132588 KB Output is correct
51 Correct 3860 ms 375548 KB Output is correct
52 Correct 3738 ms 361176 KB Output is correct
53 Correct 3733 ms 361088 KB Output is correct
54 Correct 263 ms 121228 KB Output is correct
55 Correct 231 ms 121180 KB Output is correct
56 Correct 155 ms 112048 KB Output is correct
57 Correct 65 ms 94284 KB Output is correct
58 Correct 181 ms 112248 KB Output is correct
59 Correct 235 ms 112568 KB Output is correct
60 Correct 4113 ms 324964 KB Output is correct
61 Correct 240 ms 113444 KB Output is correct
62 Correct 236 ms 113200 KB Output is correct
63 Correct 221 ms 113332 KB Output is correct
64 Correct 254 ms 114912 KB Output is correct
65 Correct 247 ms 114868 KB Output is correct
66 Correct 183 ms 112564 KB Output is correct
67 Correct 154 ms 112308 KB Output is correct
68 Correct 169 ms 113332 KB Output is correct
69 Correct 223 ms 113080 KB Output is correct
70 Correct 1536 ms 212520 KB Output is correct
71 Correct 168 ms 105140 KB Output is correct
72 Correct 1887 ms 276556 KB Output is correct
73 Correct 1022 ms 200988 KB Output is correct
74 Correct 66 ms 94280 KB Output is correct
75 Correct 62 ms 94280 KB Output is correct
76 Correct 65 ms 94160 KB Output is correct
77 Correct 67 ms 94160 KB Output is correct
78 Correct 63 ms 94280 KB Output is correct
79 Correct 73 ms 95852 KB Output is correct
80 Correct 1527 ms 184880 KB Output is correct
81 Correct 3858 ms 330428 KB Output is correct
82 Correct 4859 ms 383304 KB Output is correct
83 Execution timed out 5048 ms 480364 KB Time limit exceeded
84 Halted 0 ms 0 KB -