oj.uz

Submission #911267

# Submission time Handle Problem Language Result Execution time Memory
911267 2024-01-18T17:25:34 Z green_gold_dog Strange Device (APIO19_strange_device) C++17
35 / 100
 635 ms 100468 KB 
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 1'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

ll gcd(ll a, ll b) {
        return (min(a, b) == 0 ? max(a, b) : gcd(min(a, b), max(a, b) % min(a, b)));
}

void solve() {
        ll n, a, b;
        cin >> n >> a >> b;
        ll x = gcd(a, b + 1);
        ll mod = a * b / x;
        map<ll, ll> add;
        for (ll i = 0; i < n; i++) {
                ll l, r;
                cin >> l >> r;
                r++;
                if (r - l >= mod) {
                        cout << mod << '\n';
                        return;
                }
                l %= mod;
                r %= mod;
                if (l <= r) {
                        add[l]++;
                        add[r]--;
                } else {
                        add[0]++;
                        add[mod]--;
                        add[l]++;
                        add[r]--;
                }
        }
        ll now = 0;
        ll ans = 0;
        ll lst = 0;
        for (auto[a, b] : add) {
                if (now) {
                        ans += a - lst;
                }
                lst = a;
                now += b;
        }
        cout << ans << '\n';
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:94:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
strange_device.cpp:95:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 1372 KB Output is correct
17 Correct 49 ms 10420 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 184 ms 25428 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 530 ms 100076 KB Output is correct
3 Correct 554 ms 100380 KB Output is correct
4 Correct 634 ms 100272 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 530 ms 100076 KB Output is correct
3 Correct 554 ms 100380 KB Output is correct
4 Correct 634 ms 100272 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 532 ms 100180 KB Output is correct
7 Correct 566 ms 100436 KB Output is correct
8 Correct 544 ms 100468 KB Output is correct
9 Correct 602 ms 100256 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 530 ms 100076 KB Output is correct
3 Correct 554 ms 100380 KB Output is correct
4 Correct 634 ms 100272 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 43 ms 10444 KB Output is correct
7 Correct 43 ms 10408 KB Output is correct
8 Correct 45 ms 10320 KB Output is correct
9 Correct 50 ms 10344 KB Output is correct
10 Correct 43 ms 10356 KB Output is correct
11 Correct 43 ms 10320 KB Output is correct
12 Correct 43 ms 10308 KB Output is correct
13 Correct 51 ms 10324 KB Output is correct
14 Correct 43 ms 10212 KB Output is correct
15 Correct 51 ms 10204 KB Output is correct
16 Correct 53 ms 10320 KB Output is correct
17 Correct 57 ms 10200 KB Output is correct
18 Correct 527 ms 100164 KB Output is correct
19 Correct 581 ms 100172 KB Output is correct
20 Correct 617 ms 100084 KB Output is correct
21 Correct 47 ms 10324 KB Output is correct
22 Correct 50 ms 10324 KB Output is correct
23 Correct 82 ms 12984 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 50 ms 10392 KB Output is correct
3 Correct 50 ms 10324 KB Output is correct
4 Correct 590 ms 100128 KB Output is correct
5 Correct 51 ms 10328 KB Output is correct
6 Correct 51 ms 10320 KB Output is correct
7 Correct 51 ms 10320 KB Output is correct
8 Correct 50 ms 10272 KB Output is correct
9 Correct 49 ms 10324 KB Output is correct
10 Correct 54 ms 10316 KB Output is correct
11 Correct 48 ms 10320 KB Output is correct
12 Correct 49 ms 10576 KB Output is correct
13 Correct 53 ms 10412 KB Output is correct
14 Correct 635 ms 100084 KB Output is correct
15 Correct 43 ms 10320 KB Output is correct
16 Correct 536 ms 100340 KB Output is correct
17 Correct 518 ms 100176 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 6 ms 1372 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 500 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 4 ms 1372 KB Output is correct
17 Correct 49 ms 10420 KB Output is correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -