oj.uz

Submission #133263

# Submission time Handle Problem Language Result Execution time Memory
133263 2019-07-20T10:18:13 Z mbrc Strange Device (APIO19_strange_device) C++14
65 / 100
 731 ms 18204 KB 
#define DEBUG
// #define FASTIO

#include <cstring>
#include <cassert>
#include <utility>
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <tuple>
#include <climits>
#include <limits>
#include <deque>
#include <list>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <complex>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#define F first
#define S second 
#define pb push_back
#define endl "\n"

#ifdef FASTIO

#define pr(x) printf("%d", x)
#define ps    printf(" ")
#define endc  printf("\n")
#define pl(x) printf("%lld", x)
#define pf(x) printf("%lf", x)
#define sc(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define sf(x) scanf("%lf", &x)
#define IOS 

#endif

#ifndef FASTIO
    #define IOS { ios :: sync_with_stdio(false); cin.tie(0); }
#endif

#ifdef DEBUG
    #define dbg(s) {s;}
#endif

#ifndef DEBUG
    #define dbg(s)
#endif

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { // from [0, n-1]
    return uniform_int_distribution<int>(0, x - 1)(rng);
}

#define int ll
#define i32 int32_t
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;

inline string ps(pii z) {
    stringstream ss; ss << "[" << z.F << ", " << z.S << "]";
    return ss.str();
}

ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 

const ll mod = 1e9 + 7;

ll modexp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % mod;
        ex >>= 1ll;
        x = (x * x) % mod;
    }
    return ans;
}

const int maxn = 1e6 + 7;

const ll inf = 1e18 + 7;

vector < pii > v;

i32 main() {
    //freopen("<file>.in", "r", stdin);
    //freopen("<file>.out", "w", stdout);

    IOS;
    
    int n, A, B; cin >> n >> A >> B;
    int g = gcd(A, B + 1); A /= g;
    if (A >= inf / B) A = inf;
    else A *= B;

    int ms = A;
    int mp = -1;

    for (int j = 1; j <= n; j++) {
        int l, r; cin >> l >> r;
        if (r - l >= A) {
            cout << A + 1 << endl; return 0;
        }
        if (l <= A * (r / A)) {
            v.pb({0, r % A});
            if (l < A * (r / A))
                v.pb({l % A, A - 1});
        } else {
            v.pb({l % A, r % A});
        }
    }

    sort(all(v));
    
    int ans = 0;

    for (int j = 0; j < v.size(); ) {
        int i = j; pii ci = v[j];
        while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
            i++; ci.S = max(ci.S, v[i].S);
        }
        j = i + 1;
        ans += ci.S - ci.F + 1;
    }
    cout << ans << endl;
}

Compilation message

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:140:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < v.size(); ) {
                     ~~^~~~~~~~~~
strange_device.cpp:142:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
                ~~~~~~^~~~~~~~~~
strange_device.cpp:119:9: warning: unused variable 'ms' [-Wunused-variable]
     int ms = A;
         ^~
strange_device.cpp:120:9: warning: unused variable 'mp' [-Wunused-variable]
     int mp = -1;
         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 67 ms 2672 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 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 2 ms 348 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 524 ms 17024 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 609 ms 17020 KB Output is correct
3 Correct 610 ms 17092 KB Output is correct
4 Correct 601 ms 16956 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 609 ms 17020 KB Output is correct
3 Correct 610 ms 17092 KB Output is correct
4 Correct 601 ms 16956 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 626 ms 16948 KB Output is correct
7 Correct 607 ms 17076 KB Output is correct
8 Correct 608 ms 16956 KB Output is correct
9 Correct 660 ms 16932 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 609 ms 17020 KB Output is correct
3 Correct 610 ms 17092 KB Output is correct
4 Correct 601 ms 16956 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 61 ms 2540 KB Output is correct
7 Correct 65 ms 2680 KB Output is correct
8 Correct 62 ms 2544 KB Output is correct
9 Correct 63 ms 2488 KB Output is correct
10 Correct 64 ms 2516 KB Output is correct
11 Correct 67 ms 2516 KB Output is correct
12 Correct 61 ms 2520 KB Output is correct
13 Correct 69 ms 2672 KB Output is correct
14 Correct 63 ms 2668 KB Output is correct
15 Correct 71 ms 2668 KB Output is correct
16 Correct 70 ms 2668 KB Output is correct
17 Correct 66 ms 2672 KB Output is correct
18 Correct 639 ms 16916 KB Output is correct
19 Correct 690 ms 17080 KB Output is correct
20 Correct 674 ms 16924 KB Output is correct
21 Correct 67 ms 3184 KB Output is correct
22 Correct 60 ms 5224 KB Output is correct
23 Correct 194 ms 12716 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 67 ms 5380 KB Output is correct
3 Correct 70 ms 5224 KB Output is correct
4 Correct 731 ms 18168 KB Output is correct
5 Correct 68 ms 5608 KB Output is correct
6 Correct 68 ms 5620 KB Output is correct
7 Correct 71 ms 5752 KB Output is correct
8 Correct 69 ms 5864 KB Output is correct
9 Correct 69 ms 5780 KB Output is correct
10 Correct 68 ms 5704 KB Output is correct
11 Correct 71 ms 5480 KB Output is correct
12 Correct 67 ms 5520 KB Output is correct
13 Correct 70 ms 5524 KB Output is correct
14 Correct 657 ms 18204 KB Output is correct
15 Correct 69 ms 4948 KB Output is correct
16 Correct 607 ms 18100 KB Output is correct
17 Correct 603 ms 18132 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 67 ms 2672 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Incorrect 2 ms 376 KB Output isn't correct
21 Halted 0 ms 0 KB -