oj.uz

Submission #447439

# Submission time Handle Problem Language Result Execution time Memory
447439 2021-07-26T10:38:59 Z Mahdi Strange Device (APIO19_strange_device) C++17
15 / 100
 2333 ms 78720 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e6+5;
ll A, B, l[N], r[N], ans;
map<ll, ll>m;
int n;

void add(ll x, ll y){
    if(m.empty()){
        m.insert({x, y});
        return;
    }
    auto it=m.upper_bound(x);
    if(it!=m.begin()){
        --it;
        if(it->S>=x){
            if(it->S>=y)
                return;
            x=it->F;
            m.erase(it);
        }
        ++it;
    }
    it=m.upper_bound(x);
    while(it!=m.end()){
        if(it->S<=y)
            m.erase(it);
        else{
            if(it->F<=y){
                y=it->S;
                m.erase(it);
            }
            break;
        }
        ++it;
    }
    m.insert({x, y});
}

int main(){
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>A>>B;
    for(int i=0;i<n;++i)
        cin>>l[i]>>r[i];
    ll x=__gcd(A, B+1);
    x=A/x;
    ll inf=1e18;
    if(inf/x<B){
        for(int i=0;i<n;++i)
            ans+=r[i]-l[i]+1;
        cout<<ans;
        return 0;
    }
    B*=x;
    for(int i=0;i<n;++i){
        if(l[i]+B-1<=r[i]){
            cout<<B;
            return 0;
        }
        l[i]%=B;
        r[i]%=B;
        if(r[i]>=l[i])
            add(l[i], r[i]);
        else{
            add(l[i], B-1);
            add(0, r[i]);
        }
    }
    auto it=m.begin();
    while(it!=m.end()){
        ans+=it->S-it->F+1;
        ++it;
    }
    cout<<ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 18 ms 972 KB Output is correct
3 Correct 19 ms 1156 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 3 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1986 ms 78444 KB Output is correct
3 Correct 1968 ms 78524 KB Output is correct
4 Correct 2197 ms 78652 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1986 ms 78444 KB Output is correct
3 Correct 1968 ms 78524 KB Output is correct
4 Correct 2197 ms 78652 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1996 ms 78704 KB Output is correct
7 Correct 2012 ms 78644 KB Output is correct
8 Correct 1924 ms 78572 KB Output is correct
9 Correct 2333 ms 78720 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1986 ms 78444 KB Output is correct
3 Correct 1968 ms 78524 KB Output is correct
4 Correct 2197 ms 78652 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 195 ms 8132 KB Output is correct
7 Correct 182 ms 8216 KB Output is correct
8 Correct 175 ms 8196 KB Output is correct
9 Correct 186 ms 8280 KB Output is correct
10 Correct 185 ms 8204 KB Output is correct
11 Correct 184 ms 8212 KB Output is correct
12 Correct 187 ms 8132 KB Output is correct
13 Correct 196 ms 8216 KB Output is correct
14 Correct 185 ms 8132 KB Output is correct
15 Runtime error 141 ms 3752 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 218 ms 8044 KB Output is correct
3 Correct 194 ms 8344 KB Output is correct
4 Correct 2081 ms 78644 KB Output is correct
5 Correct 191 ms 8144 KB Output is correct
6 Correct 199 ms 8132 KB Output is correct
7 Correct 194 ms 8132 KB Output is correct
8 Correct 195 ms 8184 KB Output is correct
9 Correct 201 ms 8292 KB Output is correct
10 Correct 190 ms 8292 KB Output is correct
11 Correct 190 ms 8132 KB Output is correct
12 Correct 198 ms 8172 KB Output is correct
13 Correct 189 ms 8208 KB Output is correct
14 Runtime error 1425 ms 32228 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 18 ms 972 KB Output is correct
3 Correct 19 ms 1156 KB Output is correct
4 Runtime error 2 ms 460 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -