Submission #561304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
561304	2022-05-12T15:34:49 Z	baokhue232005	Strange Device (APIO19_strange_device)	C++14	65 / 100	435 ms	16068 KB

strange_device

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define int long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 1000005;
const ll oo = 2e18 + 7;
int n, a[maxN];
int x, y, z, k;
ii pr[maxN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> x >> y;
    x = (x / __gcd(x, y + 1));
    z = y * x;
    if(z % x) z = oo;
    if(z % y) z = oo;
    if(z == 0) z = oo;
    set<ii> st;
    for1(i, 1, n){
        cin >> x >> y;
        pr[i].fi = x % z;
        pr[i].se = y % z;
    }
    for1(i, 1, n){
        if(pr[i].fi > pr[i].se){
            ++n;
            pr[n].se = pr[i].se;
            pr[n].fi = 0;
            pr[i].se = z - 1;
        }
    }
    int lmx = -oo;
    sort(pr + 1, pr + n + 1);
    int ans = 0;
    for1(i, 1, n){
        lmx = max(lmx, pr[i].fi - 1);
        ans += max(0ll, pr[i].se - lmx);
        lmx = max(lmx, pr[i].se);
    }
    cout << ans << endl;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	4 ms	468 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	4 ms	376 KB	Output is correct
17	Correct	42 ms	1788 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 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	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	277 ms	15968 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	379 ms	15968 KB	Output is correct
3	Correct	356 ms	15908 KB	Output is correct
4	Correct	383 ms	15972 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	379 ms	15968 KB	Output is correct
3	Correct	356 ms	15908 KB	Output is correct
4	Correct	383 ms	15972 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	370 ms	16068 KB	Output is correct
7	Correct	372 ms	15848 KB	Output is correct
8	Correct	359 ms	15860 KB	Output is correct
9	Correct	406 ms	16064 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	379 ms	15968 KB	Output is correct
3	Correct	356 ms	15908 KB	Output is correct
4	Correct	383 ms	15972 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	42 ms	1832 KB	Output is correct
7	Correct	39 ms	1756 KB	Output is correct
8	Correct	39 ms	1868 KB	Output is correct
9	Correct	36 ms	1820 KB	Output is correct
10	Correct	36 ms	1880 KB	Output is correct
11	Correct	39 ms	1988 KB	Output is correct
12	Correct	36 ms	1880 KB	Output is correct
13	Correct	38 ms	1884 KB	Output is correct
14	Correct	38 ms	1820 KB	Output is correct
15	Correct	39 ms	1828 KB	Output is correct
16	Correct	41 ms	1888 KB	Output is correct
17	Correct	40 ms	1772 KB	Output is correct
18	Correct	360 ms	15944 KB	Output is correct
19	Correct	352 ms	15932 KB	Output is correct
20	Correct	402 ms	15912 KB	Output is correct
21	Correct	38 ms	1868 KB	Output is correct
22	Correct	34 ms	1800 KB	Output is correct
23	Correct	115 ms	5648 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	38 ms	1824 KB	Output is correct
3	Correct	42 ms	1888 KB	Output is correct
4	Correct	435 ms	15900 KB	Output is correct
5	Correct	38 ms	1884 KB	Output is correct
6	Correct	39 ms	1936 KB	Output is correct
7	Correct	38 ms	1876 KB	Output is correct
8	Correct	40 ms	1828 KB	Output is correct
9	Correct	40 ms	1824 KB	Output is correct
10	Correct	38 ms	1868 KB	Output is correct
11	Correct	38 ms	1868 KB	Output is correct
12	Correct	34 ms	1884 KB	Output is correct
13	Correct	38 ms	1876 KB	Output is correct
14	Correct	399 ms	16064 KB	Output is correct
15	Correct	40 ms	1780 KB	Output is correct
16	Correct	367 ms	15856 KB	Output is correct
17	Correct	370 ms	15988 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	4 ms	492 KB	Output is correct
3	Correct	4 ms	468 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	4 ms	376 KB	Output is correct
17	Correct	42 ms	1788 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #561304

Compilation message