oj.uz

Submission #252810

# Submission time Handle Problem Language Result Execution time Memory
252810 2020-07-26T10:01:28 Z orgiooo Strange Device (APIO19_strange_device) C++14
100 / 100
 2542 ms 106452 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ret return 0
#define con continue
#define db double
#define gcd __gcd
#define freopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
using namespace std;
ll n,m,ans,cnt,x,y,z,u;
ll i,j,r,l,k;
ll a[1234567],b[1234567],d[1234567],e[1234567];
map <ll,ll> f;
set<pair<ll,ll>> s;
set<int>::iterator it;
vector <ll> c[1234567];
string p,q,w;
ll lcm(ll x,ll y){
    ll z=gcd(x,y);
    return x*y/z;
}
int main(){
    ll A,B;
    cin>>n>>A>>B;
    z=A/__gcd(A,B+1);
    if (z>1e18/B){
        z=1000000000000000001;
    }else{
        z*=B;
    }
    while (n--){
        cin>>l>>r;
        if (r-l+1>=z){
            cout<<z;
            ret;
        }
        l%=z;
        r%=z;
        if (l<=r){
            s.insert({l,r});
        }else {
            s.insert({0,r});
            s.insert({l,z-1});
        }
    }
    ll mm=-1;
    while (s.size()!=0){
        auto t=*s.begin();
        s.erase(*s.begin());
        x=t.first;
        y=t.second;
        mm=max(mm,x-1);
        ans+=max(y-mm,0ll);
        mm=max(y,mm);
    }
    cout<<ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 45 ms 30328 KB Output is correct
3 Correct 43 ms 30328 KB Output is correct
4 Correct 18 ms 29312 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct
6 Correct 18 ms 29312 KB Output is correct
7 Correct 18 ms 29312 KB Output is correct
8 Correct 18 ms 29312 KB Output is correct
9 Correct 19 ms 29296 KB Output is correct
10 Correct 18 ms 29368 KB Output is correct
11 Correct 19 ms 29312 KB Output is correct
12 Correct 18 ms 29312 KB Output is correct
13 Correct 18 ms 29312 KB Output is correct
14 Correct 18 ms 29312 KB Output is correct
15 Correct 18 ms 29312 KB Output is correct
16 Correct 41 ms 30328 KB Output is correct
17 Correct 259 ms 39288 KB Output is correct
18 Correct 18 ms 29312 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 18 ms 29440 KB Output is correct
3 Correct 18 ms 29312 KB Output is correct
4 Correct 18 ms 29312 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 22 ms 29440 KB Output is correct
3 Correct 20 ms 29440 KB Output is correct
4 Correct 20 ms 29404 KB Output is correct
5 Correct 1493 ms 33388 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 2444 ms 105856 KB Output is correct
3 Correct 2473 ms 106080 KB Output is correct
4 Correct 2532 ms 105996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 2444 ms 105856 KB Output is correct
3 Correct 2473 ms 106080 KB Output is correct
4 Correct 2532 ms 105996 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct
6 Correct 2458 ms 106204 KB Output is correct
7 Correct 2440 ms 105980 KB Output is correct
8 Correct 2426 ms 105848 KB Output is correct
9 Correct 2505 ms 103560 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 2444 ms 105856 KB Output is correct
3 Correct 2473 ms 106080 KB Output is correct
4 Correct 2532 ms 105996 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct
6 Correct 266 ms 39296 KB Output is correct
7 Correct 262 ms 39288 KB Output is correct
8 Correct 252 ms 39224 KB Output is correct
9 Correct 259 ms 39416 KB Output is correct
10 Correct 257 ms 39292 KB Output is correct
11 Correct 253 ms 39288 KB Output is correct
12 Correct 260 ms 39288 KB Output is correct
13 Correct 258 ms 39288 KB Output is correct
14 Correct 266 ms 39288 KB Output is correct
15 Correct 268 ms 39288 KB Output is correct
16 Correct 260 ms 39288 KB Output is correct
17 Correct 256 ms 39416 KB Output is correct
18 Correct 2424 ms 92704 KB Output is correct
19 Correct 2454 ms 92696 KB Output is correct
20 Correct 2506 ms 92604 KB Output is correct
21 Correct 258 ms 39348 KB Output is correct
22 Correct 253 ms 39292 KB Output is correct
23 Correct 709 ms 37240 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29312 KB Output is correct
2 Correct 264 ms 39288 KB Output is correct
3 Correct 265 ms 39256 KB Output is correct
4 Correct 2483 ms 105844 KB Output is correct
5 Correct 267 ms 39292 KB Output is correct
6 Correct 272 ms 39320 KB Output is correct
7 Correct 261 ms 39416 KB Output is correct
8 Correct 259 ms 39288 KB Output is correct
9 Correct 262 ms 39284 KB Output is correct
10 Correct 274 ms 39252 KB Output is correct
11 Correct 271 ms 39288 KB Output is correct
12 Correct 262 ms 39288 KB Output is correct
13 Correct 260 ms 39288 KB Output is correct
14 Correct 2526 ms 105968 KB Output is correct
15 Correct 255 ms 39288 KB Output is correct
16 Correct 2453 ms 92512 KB Output is correct
17 Correct 2469 ms 92560 KB Output is correct
18 Correct 17 ms 29312 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29312 KB Output is correct
2 Correct 45 ms 30328 KB Output is correct
3 Correct 43 ms 30328 KB Output is correct
4 Correct 18 ms 29312 KB Output is correct
5 Correct 18 ms 29312 KB Output is correct
6 Correct 18 ms 29312 KB Output is correct
7 Correct 18 ms 29312 KB Output is correct
8 Correct 18 ms 29312 KB Output is correct
9 Correct 19 ms 29296 KB Output is correct
10 Correct 18 ms 29368 KB Output is correct
11 Correct 19 ms 29312 KB Output is correct
12 Correct 18 ms 29312 KB Output is correct
13 Correct 18 ms 29312 KB Output is correct
14 Correct 18 ms 29312 KB Output is correct
15 Correct 18 ms 29312 KB Output is correct
16 Correct 41 ms 30328 KB Output is correct
17 Correct 259 ms 39288 KB Output is correct
18 Correct 18 ms 29312 KB Output is correct
19 Correct 18 ms 29312 KB Output is correct
20 Correct 18 ms 29440 KB Output is correct
21 Correct 18 ms 29312 KB Output is correct
22 Correct 18 ms 29312 KB Output is correct
23 Correct 18 ms 29312 KB Output is correct
24 Correct 18 ms 29312 KB Output is correct
25 Correct 22 ms 29440 KB Output is correct
26 Correct 20 ms 29440 KB Output is correct
27 Correct 20 ms 29404 KB Output is correct
28 Correct 1493 ms 33388 KB Output is correct
29 Correct 18 ms 29312 KB Output is correct
30 Correct 2444 ms 105856 KB Output is correct
31 Correct 2473 ms 106080 KB Output is correct
32 Correct 2532 ms 105996 KB Output is correct
33 Correct 18 ms 29312 KB Output is correct
34 Correct 2458 ms 106204 KB Output is correct
35 Correct 2440 ms 105980 KB Output is correct
36 Correct 2426 ms 105848 KB Output is correct
37 Correct 2505 ms 103560 KB Output is correct
38 Correct 18 ms 29312 KB Output is correct
39 Correct 266 ms 39296 KB Output is correct
40 Correct 262 ms 39288 KB Output is correct
41 Correct 252 ms 39224 KB Output is correct
42 Correct 259 ms 39416 KB Output is correct
43 Correct 257 ms 39292 KB Output is correct
44 Correct 253 ms 39288 KB Output is correct
45 Correct 260 ms 39288 KB Output is correct
46 Correct 258 ms 39288 KB Output is correct
47 Correct 266 ms 39288 KB Output is correct
48 Correct 268 ms 39288 KB Output is correct
49 Correct 260 ms 39288 KB Output is correct
50 Correct 256 ms 39416 KB Output is correct
51 Correct 2424 ms 92704 KB Output is correct
52 Correct 2454 ms 92696 KB Output is correct
53 Correct 2506 ms 92604 KB Output is correct
54 Correct 258 ms 39348 KB Output is correct
55 Correct 253 ms 39292 KB Output is correct
56 Correct 709 ms 37240 KB Output is correct
57 Correct 17 ms 29312 KB Output is correct
58 Correct 264 ms 39288 KB Output is correct
59 Correct 265 ms 39256 KB Output is correct
60 Correct 2483 ms 105844 KB Output is correct
61 Correct 267 ms 39292 KB Output is correct
62 Correct 272 ms 39320 KB Output is correct
63 Correct 261 ms 39416 KB Output is correct
64 Correct 259 ms 39288 KB Output is correct
65 Correct 262 ms 39284 KB Output is correct
66 Correct 274 ms 39252 KB Output is correct
67 Correct 271 ms 39288 KB Output is correct
68 Correct 262 ms 39288 KB Output is correct
69 Correct 260 ms 39288 KB Output is correct
70 Correct 2526 ms 105968 KB Output is correct
71 Correct 255 ms 39288 KB Output is correct
72 Correct 2453 ms 92512 KB Output is correct
73 Correct 2469 ms 92560 KB Output is correct
74 Correct 17 ms 29312 KB Output is correct
75 Correct 19 ms 29312 KB Output is correct
76 Correct 17 ms 29312 KB Output is correct
77 Correct 18 ms 29328 KB Output is correct
78 Correct 18 ms 29312 KB Output is correct
79 Correct 41 ms 30264 KB Output is correct
80 Correct 2514 ms 92836 KB Output is correct
81 Correct 2492 ms 106340 KB Output is correct
82 Correct 2542 ms 92920 KB Output is correct
83 Correct 2512 ms 92924 KB Output is correct
84 Correct 2530 ms 106444 KB Output is correct
85 Correct 2476 ms 106452 KB Output is correct
86 Correct 725 ms 41976 KB Output is correct
87 Correct 17 ms 29312 KB Output is correct