oj.uz

Submission #1117186

# Submission time Handle Problem Language Result Execution time Memory
1117186 2024-11-22T21:35:47 Z PagodePaiva Strange Device (APIO19_strange_device) C++17
70 / 100
 5000 ms 423128 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;
    vector <pair <long long, long long>> v;
    map <long long ,int> cnt;
    long long add = 0;
    //cout << "cte:\n";
    for(auto [l, r] : queries){
        //cout << l << ' ' << r << '\n';
        v.push_back({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;
    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 94324 KB Output is correct
2 Correct 63 ms 95044 KB Output is correct
3 Correct 67 ms 95392 KB Output is correct
4 Correct 64 ms 94200 KB Output is correct
5 Correct 70 ms 94284 KB Output is correct
6 Correct 64 ms 94312 KB Output is correct
7 Correct 68 ms 94280 KB Output is correct
8 Correct 62 ms 94280 KB Output is correct
9 Correct 62 ms 94292 KB Output is correct
10 Correct 74 ms 94252 KB Output is correct
11 Correct 67 ms 94280 KB Output is correct
12 Correct 65 ms 94280 KB Output is correct
13 Correct 67 ms 94280 KB Output is correct
14 Correct 65 ms 94280 KB Output is correct
15 Correct 62 ms 94288 KB Output is correct
16 Correct 69 ms 94992 KB Output is correct
17 Correct 159 ms 102068 KB Output is correct
18 Correct 70 ms 94280 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 94280 KB Output is correct
2 Correct 64 ms 94272 KB Output is correct
3 Correct 67 ms 94280 KB Output is correct
4 Correct 65 ms 94280 KB Output is correct
5 Correct 69 ms 94300 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 94280 KB Output is correct
2 Correct 62 ms 94536 KB Output is correct
3 Correct 68 ms 94416 KB Output is correct
4 Correct 64 ms 94536 KB Output is correct
5 Correct 292 ms 134560 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94280 KB Output is correct
2 Correct 673 ms 212408 KB Output is correct
3 Correct 388 ms 142052 KB Output is correct
4 Correct 406 ms 142020 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94280 KB Output is correct
2 Correct 673 ms 212408 KB Output is correct
3 Correct 388 ms 142052 KB Output is correct
4 Correct 406 ms 142020 KB Output is correct
5 Correct 55 ms 94320 KB Output is correct
6 Correct 1494 ms 298396 KB Output is correct
7 Correct 670 ms 184960 KB Output is correct
8 Correct 1604 ms 298684 KB Output is correct
9 Correct 1676 ms 298724 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 94280 KB Output is correct
2 Correct 673 ms 212408 KB Output is correct
3 Correct 388 ms 142052 KB Output is correct
4 Correct 406 ms 142020 KB Output is correct
5 Correct 63 ms 94280 KB Output is correct
6 Correct 141 ms 112052 KB Output is correct
7 Correct 176 ms 115640 KB Output is correct
8 Correct 167 ms 115676 KB Output is correct
9 Correct 183 ms 115640 KB Output is correct
10 Correct 160 ms 110772 KB Output is correct
11 Correct 179 ms 116576 KB Output is correct
12 Correct 176 ms 115640 KB Output is correct
13 Correct 217 ms 115132 KB Output is correct
14 Correct 165 ms 112384 KB Output is correct
15 Correct 236 ms 113596 KB Output is correct
16 Correct 219 ms 112580 KB Output is correct
17 Correct 350 ms 127128 KB Output is correct
18 Correct 2216 ms 320572 KB Output is correct
19 Correct 2377 ms 305664 KB Output is correct
20 Correct 2478 ms 305600 KB Output is correct
21 Correct 199 ms 115384 KB Output is correct
22 Correct 185 ms 115388 KB Output is correct
23 Correct 164 ms 112048 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94124 KB Output is correct
2 Correct 171 ms 112308 KB Output is correct
3 Correct 218 ms 112412 KB Output is correct
4 Correct 3984 ms 322924 KB Output is correct
5 Correct 224 ms 113136 KB Output is correct
6 Correct 218 ms 113336 KB Output is correct
7 Correct 239 ms 113332 KB Output is correct
8 Correct 287 ms 114808 KB Output is correct
9 Correct 277 ms 114792 KB Output is correct
10 Correct 190 ms 112316 KB Output is correct
11 Correct 153 ms 112308 KB Output is correct
12 Correct 183 ms 112308 KB Output is correct
13 Correct 262 ms 112828 KB Output is correct
14 Correct 1521 ms 211828 KB Output is correct
15 Correct 183 ms 104828 KB Output is correct
16 Correct 2053 ms 274356 KB Output is correct
17 Correct 1071 ms 198568 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 54 ms 94324 KB Output is correct
2 Correct 63 ms 95044 KB Output is correct
3 Correct 67 ms 95392 KB Output is correct
4 Correct 64 ms 94200 KB Output is correct
5 Correct 70 ms 94284 KB Output is correct
6 Correct 64 ms 94312 KB Output is correct
7 Correct 68 ms 94280 KB Output is correct
8 Correct 62 ms 94280 KB Output is correct
9 Correct 62 ms 94292 KB Output is correct
10 Correct 74 ms 94252 KB Output is correct
11 Correct 67 ms 94280 KB Output is correct
12 Correct 65 ms 94280 KB Output is correct
13 Correct 67 ms 94280 KB Output is correct
14 Correct 65 ms 94280 KB Output is correct
15 Correct 62 ms 94288 KB Output is correct
16 Correct 69 ms 94992 KB Output is correct
17 Correct 159 ms 102068 KB Output is correct
18 Correct 70 ms 94280 KB Output is correct
19 Correct 62 ms 94280 KB Output is correct
20 Correct 64 ms 94272 KB Output is correct
21 Correct 67 ms 94280 KB Output is correct
22 Correct 65 ms 94280 KB Output is correct
23 Correct 69 ms 94300 KB Output is correct
24 Correct 61 ms 94280 KB Output is correct
25 Correct 62 ms 94536 KB Output is correct
26 Correct 68 ms 94416 KB Output is correct
27 Correct 64 ms 94536 KB Output is correct
28 Correct 292 ms 134560 KB Output is correct
29 Correct 59 ms 94280 KB Output is correct
30 Correct 673 ms 212408 KB Output is correct
31 Correct 388 ms 142052 KB Output is correct
32 Correct 406 ms 142020 KB Output is correct
33 Correct 55 ms 94320 KB Output is correct
34 Correct 1494 ms 298396 KB Output is correct
35 Correct 670 ms 184960 KB Output is correct
36 Correct 1604 ms 298684 KB Output is correct
37 Correct 1676 ms 298724 KB Output is correct
38 Correct 63 ms 94280 KB Output is correct
39 Correct 141 ms 112052 KB Output is correct
40 Correct 176 ms 115640 KB Output is correct
41 Correct 167 ms 115676 KB Output is correct
42 Correct 183 ms 115640 KB Output is correct
43 Correct 160 ms 110772 KB Output is correct
44 Correct 179 ms 116576 KB Output is correct
45 Correct 176 ms 115640 KB Output is correct
46 Correct 217 ms 115132 KB Output is correct
47 Correct 165 ms 112384 KB Output is correct
48 Correct 236 ms 113596 KB Output is correct
49 Correct 219 ms 112580 KB Output is correct
50 Correct 350 ms 127128 KB Output is correct
51 Correct 2216 ms 320572 KB Output is correct
52 Correct 2377 ms 305664 KB Output is correct
53 Correct 2478 ms 305600 KB Output is correct
54 Correct 199 ms 115384 KB Output is correct
55 Correct 185 ms 115388 KB Output is correct
56 Correct 164 ms 112048 KB Output is correct
57 Correct 64 ms 94124 KB Output is correct
58 Correct 171 ms 112308 KB Output is correct
59 Correct 218 ms 112412 KB Output is correct
60 Correct 3984 ms 322924 KB Output is correct
61 Correct 224 ms 113136 KB Output is correct
62 Correct 218 ms 113336 KB Output is correct
63 Correct 239 ms 113332 KB Output is correct
64 Correct 287 ms 114808 KB Output is correct
65 Correct 277 ms 114792 KB Output is correct
66 Correct 190 ms 112316 KB Output is correct
67 Correct 153 ms 112308 KB Output is correct
68 Correct 183 ms 112308 KB Output is correct
69 Correct 262 ms 112828 KB Output is correct
70 Correct 1521 ms 211828 KB Output is correct
71 Correct 183 ms 104828 KB Output is correct
72 Correct 2053 ms 274356 KB Output is correct
73 Correct 1071 ms 198568 KB Output is correct
74 Correct 66 ms 94280 KB Output is correct
75 Correct 78 ms 94280 KB Output is correct
76 Correct 74 ms 94280 KB Output is correct
77 Correct 68 ms 94252 KB Output is correct
78 Correct 68 ms 94280 KB Output is correct
79 Correct 76 ms 95824 KB Output is correct
80 Correct 1680 ms 176676 KB Output is correct
81 Correct 3911 ms 322808 KB Output is correct
82 Correct 3280 ms 325764 KB Output is correct
83 Execution timed out 5073 ms 423128 KB Time limit exceeded
84 Halted 0 ms 0 KB -