oj.uz

Submission #217924

# Submission time Handle Problem Language Result Execution time Memory
217924 2020-03-31T08:26:49 Z Autoratch Strange Device (APIO19_strange_device) C++14
10 / 100
 1494 ms 141584 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n;
long long a,b;
map<long long,int> ma;
set<long long> s;
int res[N];
vector<pair<long long,long long> > in;
long long rng[N],ans;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> a >> b;
    if(a>1e18/b) a = (1e18+2),b = 1;
    for(int i = 0;i < n;i++)
    {
        long long x,y;
        cin >> x >> y; 
        if(y-x+1LL>=a*b){ cout << a*b; return 0; }
        y++;
        x%=(a*b),y%=(a*b); 
        if(y<x) in.push_back({0LL,y}),in.push_back({x,a*b});
        else in.push_back({x,y});
        s.insert(x),s.insert(y);
    }
    s.insert(0),s.insert(a*b);
    long long prev = 0;
    int id = 0;
    for(auto x : s) ma[x] = ++id,rng[id-1] = x-prev,prev = x;
    for(auto x : in) res[ma[x.first]]++,res[ma[x.second]]--;
    for(int i = 1;i < N;i++) res[i]+=res[i-1];
    for(int i = 1;i < N;i++) if(res[i]) ans+=rng[i];
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 28 ms 9948 KB Output is correct
3 Correct 25 ms 9972 KB Output is correct
4 Incorrect 15 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 15 ms 8192 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 19 ms 8448 KB Output is correct
3 Correct 17 ms 8436 KB Output is correct
4 Correct 19 ms 8320 KB Output is correct
5 Correct 385 ms 24000 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1349 ms 141216 KB Output is correct
3 Incorrect 1398 ms 141372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1349 ms 141216 KB Output is correct
3 Incorrect 1398 ms 141372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 1349 ms 141216 KB Output is correct
3 Incorrect 1398 ms 141372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 146 ms 21600 KB Output is correct
3 Correct 142 ms 21732 KB Output is correct
4 Correct 1494 ms 141548 KB Output is correct
5 Correct 136 ms 22116 KB Output is correct
6 Correct 143 ms 22052 KB Output is correct
7 Correct 162 ms 22092 KB Output is correct
8 Correct 148 ms 22116 KB Output is correct
9 Correct 141 ms 22116 KB Output is correct
10 Correct 151 ms 22116 KB Output is correct
11 Correct 185 ms 22116 KB Output is correct
12 Correct 136 ms 22116 KB Output is correct
13 Correct 143 ms 22116 KB Output is correct
14 Correct 1450 ms 141584 KB Output is correct
15 Incorrect 146 ms 22116 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 28 ms 9948 KB Output is correct
3 Correct 25 ms 9972 KB Output is correct
4 Incorrect 15 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -