oj.uz

Submission #1091876

# Submission time Handle Problem Language Result Execution time Memory
1091876 2024-09-22T12:24:42 Z mispertion Strange Device (APIO19_strange_device) C++17
35 / 100
 585 ms 100436 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int ll
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 1e6 + 1;
const int M = 50 + 1;
const int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 31;

int mult(int a, int b) {
    return a * 1LL * b % mod;
}

int sum(int a, int b) { 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}

ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

int n, A, B;
map<int, int> mp;

void solve(){
    cin >> n >> A >> B;
    int ccl = A / __gcd(A, B + 1) * B;
    for(int i = 1; i <= n; i++){
        int l, r;
        cin >> l >> r;
        if(r - l + 1 >= ccl){
            mp[0]++;
            mp[ccl]--;
        }else{
            if(l % ccl <= r % ccl){
                mp[l % ccl]++;
                mp[r % ccl + 1]--;
            }else{
                mp[l % ccl]++;
                mp[ccl]--;
                mp[0]++;
                mp[r % ccl + 1]--;
            }
        }
    }
    int cur = 0, ans = 0;
    for(auto it = mp.begin(); it != (--mp.end()); it++){
        auto it1 = it;
        it1++;
        cur += it->S;
        if(cur != 0)
            ans += (it1->F - it->F);
    }
    cout << ans << '\n';
}   

signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 7 ms 1372 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1392 KB Output is correct
17 Correct 42 ms 10424 KB Output is correct
18 Incorrect 0 ms 344 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 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 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 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 152 ms 25524 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 452 ms 100064 KB Output is correct
3 Correct 476 ms 100056 KB Output is correct
4 Correct 549 ms 100180 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 452 ms 100064 KB Output is correct
3 Correct 476 ms 100056 KB Output is correct
4 Correct 549 ms 100180 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 529 ms 100112 KB Output is correct
7 Correct 536 ms 100180 KB Output is correct
8 Correct 471 ms 100160 KB Output is correct
9 Correct 585 ms 100180 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 452 ms 100064 KB Output is correct
3 Correct 476 ms 100056 KB Output is correct
4 Correct 549 ms 100180 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 38 ms 10412 KB Output is correct
7 Correct 39 ms 10324 KB Output is correct
8 Correct 48 ms 10320 KB Output is correct
9 Correct 48 ms 10320 KB Output is correct
10 Correct 40 ms 10320 KB Output is correct
11 Correct 39 ms 10248 KB Output is correct
12 Correct 42 ms 10216 KB Output is correct
13 Correct 48 ms 10420 KB Output is correct
14 Correct 43 ms 10320 KB Output is correct
15 Correct 47 ms 10324 KB Output is correct
16 Correct 50 ms 10432 KB Output is correct
17 Correct 42 ms 10408 KB Output is correct
18 Correct 464 ms 100048 KB Output is correct
19 Correct 501 ms 100136 KB Output is correct
20 Correct 531 ms 100172 KB Output is correct
21 Correct 39 ms 10324 KB Output is correct
22 Correct 41 ms 10324 KB Output is correct
23 Correct 71 ms 12976 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 45 ms 10216 KB Output is correct
3 Correct 45 ms 10320 KB Output is correct
4 Correct 551 ms 100188 KB Output is correct
5 Correct 50 ms 10324 KB Output is correct
6 Correct 49 ms 10324 KB Output is correct
7 Correct 48 ms 10320 KB Output is correct
8 Correct 49 ms 10316 KB Output is correct
9 Correct 50 ms 10324 KB Output is correct
10 Correct 44 ms 10324 KB Output is correct
11 Correct 44 ms 10324 KB Output is correct
12 Correct 45 ms 10324 KB Output is correct
13 Correct 52 ms 10256 KB Output is correct
14 Correct 585 ms 100176 KB Output is correct
15 Correct 41 ms 10420 KB Output is correct
16 Correct 539 ms 100224 KB Output is correct
17 Correct 490 ms 100436 KB Output is correct
18 Incorrect 1 ms 344 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 7 ms 1372 KB Output is correct
3 Correct 4 ms 1372 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1392 KB Output is correct
17 Correct 42 ms 10424 KB Output is correct
18 Incorrect 0 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -