oj.uz

Submission #806605

# Submission time Handle Problem Language Result Execution time Memory
806605 2023-08-04T08:17:27 Z gg123_pe Strange Device (APIO19_strange_device) C++14
10 / 100
 1162 ms 78568 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"; 
}
ll gcd(ll x, ll y){
    if(x > y) swap(x, y); 
    if(y%x == 0) return x; 
    return gcd(y - (y/x) * x, y); 
}
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 0 ms 212 KB Output is correct
2 Incorrect 15 ms 1444 KB Output isn't correct
3 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 212 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 ms 340 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 1 ms 212 KB Output is correct
2 Correct 1051 ms 78532 KB Output is correct
3 Correct 1057 ms 78556 KB Output is correct
4 Correct 1077 ms 78544 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 1051 ms 78532 KB Output is correct
3 Correct 1057 ms 78556 KB Output is correct
4 Correct 1077 ms 78544 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1077 ms 78448 KB Output is correct
7 Correct 1115 ms 78496 KB Output is correct
8 Correct 1058 ms 78512 KB Output is correct
9 Correct 1162 ms 78568 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1051 ms 78532 KB Output is correct
3 Correct 1057 ms 78556 KB Output is correct
4 Correct 1077 ms 78544 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 95 ms 4664 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 30.0

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