oj.uz

Submission #561302

# Submission time Handle Problem Language Result Execution time Memory
561302 2022-05-12T15:33:47 Z baokhue232005 Strange Device (APIO19_strange_device) C++14
65 / 100
 442 ms 18176 KB 
/*
#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;
    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 1 ms 340 KB Output is correct
2 Correct 4 ms 752 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 5 ms 840 KB Output is correct
17 Correct 42 ms 2904 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 332 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 328 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 267 ms 17048 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 369 ms 16688 KB Output is correct
3 Correct 367 ms 16696 KB Output is correct
4 Correct 399 ms 18176 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 369 ms 16688 KB Output is correct
3 Correct 367 ms 16696 KB Output is correct
4 Correct 399 ms 18176 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 383 ms 18096 KB Output is correct
7 Correct 380 ms 18044 KB Output is correct
8 Correct 392 ms 18024 KB Output is correct
9 Correct 427 ms 17932 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 369 ms 16688 KB Output is correct
3 Correct 367 ms 16696 KB Output is correct
4 Correct 399 ms 18176 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 42 ms 2808 KB Output is correct
7 Correct 42 ms 2796 KB Output is correct
8 Correct 37 ms 2864 KB Output is correct
9 Correct 41 ms 2848 KB Output is correct
10 Correct 46 ms 2868 KB Output is correct
11 Correct 41 ms 2908 KB Output is correct
12 Correct 40 ms 2824 KB Output is correct
13 Correct 42 ms 2820 KB Output is correct
14 Correct 41 ms 2896 KB Output is correct
15 Correct 44 ms 2836 KB Output is correct
16 Correct 42 ms 2896 KB Output is correct
17 Correct 42 ms 2784 KB Output is correct
18 Correct 380 ms 17632 KB Output is correct
19 Correct 376 ms 17992 KB Output is correct
20 Correct 442 ms 18124 KB Output is correct
21 Correct 43 ms 2904 KB Output is correct
22 Correct 48 ms 2848 KB Output is correct
23 Correct 118 ms 6440 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 48 ms 2884 KB Output is correct
3 Correct 54 ms 2888 KB Output is correct
4 Correct 442 ms 16664 KB Output is correct
5 Correct 42 ms 2832 KB Output is correct
6 Correct 43 ms 2880 KB Output is correct
7 Correct 44 ms 2924 KB Output is correct
8 Correct 43 ms 2864 KB Output is correct
9 Correct 44 ms 2944 KB Output is correct
10 Correct 40 ms 2796 KB Output is correct
11 Correct 43 ms 2820 KB Output is correct
12 Correct 40 ms 2852 KB Output is correct
13 Correct 44 ms 2872 KB Output is correct
14 Correct 414 ms 18004 KB Output is correct
15 Correct 45 ms 2872 KB Output is correct
16 Correct 373 ms 17628 KB Output is correct
17 Correct 384 ms 17940 KB Output is correct
18 Correct 0 ms 328 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 4 ms 752 KB Output is correct
3 Correct 5 ms 856 KB Output is correct
4 Correct 1 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 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 5 ms 840 KB Output is correct
17 Correct 42 ms 2904 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Incorrect 1 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -