Submission #683683

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683683	2023-01-19T05:26:35 Z	Nursik	Strange Device (APIO19_strange_device)	C++17	65 / 100	439 ms	32772 KB

strange_device

#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
#define bug cout << "bug\n";

const ll maxn = 1e6 + 5, maxm = 2e2 + 1;
const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 126067, base = 1000050017,
         biginf = 5e18;
const ld eps = 1e-15;
using namespace std;

int n;
ll a, b, p;
ll l[maxn], r[maxn];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a >> b;
    a = a / gcd(a, b + 1);
    if (a > 1e18 / b){
        p = 1e18;
    }
    else{
        p = a * b;
    }
    vector<pair<ll, ll>> v;
    for (int i = 1; i <= n; ++i){
        cin >> l[i] >> r[i];
        ll x = l[i] % p;
        ll y = r[i] % p;
        /*if (r[i] - l[i] + 1 >= p){
            cout << p;
            exit(0);
        }*/
        if (x <= y){
            v.pb(mp(x, y));
        }
        else{
            v.pb(mp(x, p - 1));
            v.pb(mp(0, y));
        }
    }
    sort(v.begin(), v.end());
    ll ans = 0, nxt = -1;
    for (auto it : v){
        ll lf = it.f, rg = it.s;
        if (nxt < lf){
            ans += rg - lf + 1;
            nxt = rg;
        }
        else if (nxt <= rg){
            ans += rg - nxt;
            nxt = rg;
        }
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	5 ms	1108 KB	Output is correct
3	Correct	6 ms	1236 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	5 ms	1156 KB	Output is correct
17	Correct	43 ms	4412 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	298 ms	32460 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	388 ms	32540 KB	Output is correct
3	Correct	389 ms	32172 KB	Output is correct
4	Correct	368 ms	32228 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	388 ms	32540 KB	Output is correct
3	Correct	389 ms	32172 KB	Output is correct
4	Correct	368 ms	32228 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	388 ms	32236 KB	Output is correct
7	Correct	436 ms	32096 KB	Output is correct
8	Correct	373 ms	32084 KB	Output is correct
9	Correct	419 ms	32152 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	388 ms	32540 KB	Output is correct
3	Correct	389 ms	32172 KB	Output is correct
4	Correct	368 ms	32228 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	43 ms	4296 KB	Output is correct
7	Correct	46 ms	4336 KB	Output is correct
8	Correct	41 ms	4320 KB	Output is correct
9	Correct	43 ms	4328 KB	Output is correct
10	Correct	43 ms	4256 KB	Output is correct
11	Correct	43 ms	4316 KB	Output is correct
12	Correct	38 ms	4312 KB	Output is correct
13	Correct	40 ms	4376 KB	Output is correct
14	Correct	41 ms	4280 KB	Output is correct
15	Correct	47 ms	4260 KB	Output is correct
16	Correct	43 ms	4272 KB	Output is correct
17	Correct	41 ms	4288 KB	Output is correct
18	Correct	378 ms	32368 KB	Output is correct
19	Correct	384 ms	32428 KB	Output is correct
20	Correct	436 ms	32284 KB	Output is correct
21	Correct	39 ms	4292 KB	Output is correct
22	Correct	36 ms	4296 KB	Output is correct
23	Correct	123 ms	13696 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	46 ms	4576 KB	Output is correct
3	Correct	42 ms	4512 KB	Output is correct
4	Correct	439 ms	32772 KB	Output is correct
5	Correct	39 ms	4348 KB	Output is correct
6	Correct	40 ms	4316 KB	Output is correct
7	Correct	42 ms	4284 KB	Output is correct
8	Correct	43 ms	4304 KB	Output is correct
9	Correct	45 ms	4288 KB	Output is correct
10	Correct	42 ms	4084 KB	Output is correct
11	Correct	42 ms	3996 KB	Output is correct
12	Correct	39 ms	4040 KB	Output is correct
13	Correct	49 ms	4072 KB	Output is correct
14	Correct	410 ms	32252 KB	Output is correct
15	Correct	40 ms	4076 KB	Output is correct
16	Correct	376 ms	32276 KB	Output is correct
17	Correct	413 ms	32096 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	5 ms	1108 KB	Output is correct
3	Correct	6 ms	1236 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	328 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	5 ms	1156 KB	Output is correct
17	Correct	43 ms	4412 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #683683

Compilation message