oj.uz

Submission #806590

# Submission time Handle Problem Language Result Execution time Memory
806590 2023-08-04T08:10:59 Z gg123_pe Strange Device (APIO19_strange_device) C++14
35 / 100
 1376 ms 115764 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e6 + 5; 
const ll inf = 1e18 + 5; 

int n; 
ll l[N], r[N]; 
ll A, B, S; 

void subtask_1(){
    set <pair<ll,ll>> s;

    f(i,1,n+1){
        for(ll j = l[i]; j <= r[i]; j++){
            ll a, b; 
            a = (j + j/B) % A; 
            b = j % B; 
            s.insert({a, b}); 
        }
    }
    cout << s.size() << "\n"; 
}
void solve(){
    ll X = A / __gcd(A, B+1);  
    ll period = X * B;  

    set <pair<ll,ll>> s; 

    f(i,1,n+1){
        ll len = r[i] - l[i] + 1;  
        if(len >= period){
            cout << period << "\n"; 
            return; 
        }
        ll x = l[i] % period;
        if(len > period-x){
            s.insert({x, period-1}); 
            s.insert({0, r[i]%period}); 
        }   
        else{
            s.insert({x, r[i]%period}); 
        }
    }
    ll ans = 0, l, r;
    auto it = s.begin(); 
    l = it->first, r = it->second; 
    for(auto p: s){
        if(p == *it) continue; 
        ll x = p.first, y = p.second; 

        if(x <= r){
            r = max(r, y); 
        }
        else if(x == r+1){
            r = y; 
        }
        else{
            ans += r - l + 1; 
            l = x, r = y; 
        }
    }
    ans += r - l + 1; 
    cout << ans << "\n"; 
}
int main(){
    cin >> n >> A >> B; 

    f(i,1,n+1){
        cin >> l[i] >> r[i]; 
    }

    solve(); 
    
    return 0; 
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 11 ms 1364 KB Output is correct
3 Correct 17 ms 1364 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 16 ms 1364 KB Output is correct
17 Correct 110 ms 11848 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 1 ms 308 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 712 ms 41092 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1137 ms 115680 KB Output is correct
3 Correct 1200 ms 115692 KB Output is correct
4 Correct 1152 ms 115720 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1137 ms 115680 KB Output is correct
3 Correct 1200 ms 115692 KB Output is correct
4 Correct 1152 ms 115720 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1173 ms 115720 KB Output is correct
7 Correct 1141 ms 115696 KB Output is correct
8 Correct 1195 ms 115752 KB Output is correct
9 Correct 1235 ms 115728 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1137 ms 115680 KB Output is correct
3 Correct 1200 ms 115692 KB Output is correct
4 Correct 1152 ms 115720 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 124 ms 11732 KB Output is correct
7 Correct 113 ms 11776 KB Output is correct
8 Correct 109 ms 11844 KB Output is correct
9 Correct 109 ms 11796 KB Output is correct
10 Correct 120 ms 11824 KB Output is correct
11 Correct 106 ms 11812 KB Output is correct
12 Correct 121 ms 11852 KB Output is correct
13 Correct 108 ms 11836 KB Output is correct
14 Correct 107 ms 11740 KB Output is correct
15 Correct 110 ms 11760 KB Output is correct
16 Correct 110 ms 11776 KB Output is correct
17 Correct 138 ms 11820 KB Output is correct
18 Correct 1119 ms 115764 KB Output is correct
19 Correct 1149 ms 115632 KB Output is correct
20 Correct 1211 ms 115724 KB Output is correct
21 Correct 134 ms 11836 KB Output is correct
22 Correct 110 ms 11796 KB Output is correct
23 Correct 324 ms 18244 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 109 ms 11840 KB Output is correct
3 Correct 117 ms 11744 KB Output is correct
4 Correct 1190 ms 115756 KB Output is correct
5 Correct 110 ms 11852 KB Output is correct
6 Correct 115 ms 11732 KB Output is correct
7 Correct 113 ms 11784 KB Output is correct
8 Correct 117 ms 11880 KB Output is correct
9 Correct 109 ms 11756 KB Output is correct
10 Correct 109 ms 11764 KB Output is correct
11 Correct 107 ms 11756 KB Output is correct
12 Correct 108 ms 11768 KB Output is correct
13 Correct 111 ms 11780 KB Output is correct
14 Correct 1376 ms 115744 KB Output is correct
15 Correct 129 ms 11788 KB Output is correct
16 Correct 1105 ms 115728 KB Output is correct
17 Correct 1127 ms 115700 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 11 ms 1364 KB Output is correct
3 Correct 17 ms 1364 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 308 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 16 ms 1364 KB Output is correct
17 Correct 110 ms 11848 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -