oj.uz

Submission #217922

# Submission time Handle Problem Language Result Execution time Memory
217922 2020-03-31T08:25:12 Z Autoratch Strange Device (APIO19_strange_device) C++14
10 / 100
 1463 ms 141628 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,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 26 ms 9892 KB Output is correct
3 Correct 27 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 5 ms 384 KB Output is correct
3 Correct 15 ms 8192 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 17 ms 8192 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 17 ms 8448 KB Output is correct
3 Correct 16 ms 8320 KB Output is correct
4 Correct 17 ms 8320 KB Output is correct
5 Correct 416 ms 25016 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 356 KB Output is correct
2 Correct 1379 ms 141432 KB Output is correct
3 Incorrect 1410 ms 141540 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 356 KB Output is correct
2 Correct 1379 ms 141432 KB Output is correct
3 Incorrect 1410 ms 141540 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 356 KB Output is correct
2 Correct 1379 ms 141432 KB Output is correct
3 Incorrect 1410 ms 141540 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 171 ms 23244 KB Output is correct
3 Correct 142 ms 22880 KB Output is correct
4 Correct 1424 ms 141628 KB Output is correct
5 Correct 149 ms 23140 KB Output is correct
6 Correct 154 ms 22968 KB Output is correct
7 Correct 137 ms 22884 KB Output is correct
8 Correct 144 ms 22884 KB Output is correct
9 Correct 149 ms 22884 KB Output is correct
10 Correct 139 ms 22884 KB Output is correct
11 Correct 143 ms 23012 KB Output is correct
12 Correct 149 ms 22884 KB Output is correct
13 Correct 155 ms 23116 KB Output is correct
14 Correct 1463 ms 141628 KB Output is correct
15 Incorrect 150 ms 22884 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 26 ms 9892 KB Output is correct
3 Correct 27 ms 9972 KB Output is correct
4 Incorrect 15 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -