Submission #683671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683671	2023-01-19T05:17:49 Z	Nursik	Strange Device (APIO19_strange_device)	C++17	65 / 100	460 ms	44668 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;
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);
    ll p;
    if (a > (1e18 + b - 1) / 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 (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	1 ms	340 KB	Output is correct
2	Correct	5 ms	1120 KB	Output is correct
3	Correct	5 ms	1160 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	324 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	0 ms	328 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	56 ms	7216 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 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	344 KB	Output is correct
5	Correct	334 ms	44668 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	396 ms	36544 KB	Output is correct
3	Correct	411 ms	32548 KB	Output is correct
4	Correct	372 ms	32632 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	396 ms	36544 KB	Output is correct
3	Correct	411 ms	32548 KB	Output is correct
4	Correct	372 ms	32632 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	380 ms	32548 KB	Output is correct
7	Correct	377 ms	32632 KB	Output is correct
8	Correct	403 ms	32516 KB	Output is correct
9	Correct	401 ms	32524 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	396 ms	36544 KB	Output is correct
3	Correct	411 ms	32548 KB	Output is correct
4	Correct	372 ms	32632 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	42 ms	7216 KB	Output is correct
7	Correct	50 ms	7180 KB	Output is correct
8	Correct	39 ms	7232 KB	Output is correct
9	Correct	40 ms	7332 KB	Output is correct
10	Correct	39 ms	7276 KB	Output is correct
11	Correct	42 ms	7184 KB	Output is correct
12	Correct	41 ms	7204 KB	Output is correct
13	Correct	42 ms	7228 KB	Output is correct
14	Correct	40 ms	7228 KB	Output is correct
15	Correct	46 ms	7324 KB	Output is correct
16	Correct	41 ms	7212 KB	Output is correct
17	Correct	67 ms	7260 KB	Output is correct
18	Correct	396 ms	32472 KB	Output is correct
19	Correct	390 ms	32420 KB	Output is correct
20	Correct	423 ms	32280 KB	Output is correct
21	Correct	42 ms	7232 KB	Output is correct
22	Correct	39 ms	7240 KB	Output is correct
23	Correct	121 ms	18332 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	41 ms	4692 KB	Output is correct
3	Correct	41 ms	4692 KB	Output is correct
4	Correct	460 ms	33036 KB	Output is correct
5	Correct	51 ms	7292 KB	Output is correct
6	Correct	42 ms	7260 KB	Output is correct
7	Correct	42 ms	7200 KB	Output is correct
8	Correct	50 ms	7292 KB	Output is correct
9	Correct	46 ms	7236 KB	Output is correct
10	Correct	49 ms	7288 KB	Output is correct
11	Correct	47 ms	7272 KB	Output is correct
12	Correct	41 ms	7216 KB	Output is correct
13	Correct	45 ms	7236 KB	Output is correct
14	Correct	441 ms	32124 KB	Output is correct
15	Correct	43 ms	7216 KB	Output is correct
16	Correct	380 ms	32112 KB	Output is correct
17	Correct	375 ms	31860 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	1 ms	340 KB	Output is correct
2	Correct	5 ms	1120 KB	Output is correct
3	Correct	5 ms	1160 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	324 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	0 ms	328 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	328 KB	Output is correct
16	Correct	6 ms	1236 KB	Output is correct
17	Correct	56 ms	7216 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Incorrect	1 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #683671

Compilation message