oj.uz

Submission #953877

# Submission time Handle Problem Language Result Execution time Memory
953877 2024-03-26T18:53:22 Z Vladth11 Strange Device (APIO19_strange_device) C++14
10 / 100
 564 ms 70676 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 300001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;

const ll VALMAX = 2e18;

signed main() {
#ifdef HOME
    ifstream cin(".in");
    ofstream cout(".out");
#endif // HOME
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll a, b;
    cin >> n >> a >> b;
    ll period;
    if(a >= VALMAX / b){
        period = VALMAX;
    }else{
        period = a * b;
    }
    vector <pii> events;
    while(n--){
        ll l, r;
        cin >> l >> r;
        if(r - l + 1 >= period){
            events.push_back({0, 1});
            events.push_back({period, -1});
            continue;
        }
        l %= period;
        r %= period;
        if(l <= r){
            events.push_back({l, 1});
            events.push_back({r + 1, -1});
        }else{
            events.push_back({0, 1});
            events.push_back({r + 1, -1});
            events.push_back({l, 1});
            events.push_back({period, -1});
        }
    }
    int s = 0;
    ll total = 0;
    sort(events.begin(), events.end());
    for(int i = 0; i < events.size(); i++){
        s += events[i].second;
        if(events[i].first < period && (i < (events.size() - 1))){
            if(s > 0)
                total += (min(period, events[i + 1].first) - events[i].first);
        }
    }
    cout << total;
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < events.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
strange_device.cpp:61:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(events[i].first < period && (i < (events.size() - 1))){
      |                                         ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
5.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 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

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 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 261 ms 58380 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 416 ms 69268 KB Output is correct
3 Incorrect 377 ms 70676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 416 ms 69268 KB Output is correct
3 Incorrect 377 ms 70676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 416 ms 69268 KB Output is correct
3 Incorrect 377 ms 70676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 46 ms 8276 KB Output is correct
3 Correct 44 ms 8644 KB Output is correct
4 Correct 564 ms 69796 KB Output is correct
5 Correct 55 ms 7624 KB Output is correct
6 Correct 47 ms 8392 KB Output is correct
7 Correct 44 ms 8900 KB Output is correct
8 Correct 48 ms 7284 KB Output is correct
9 Correct 42 ms 7784 KB Output is correct
10 Correct 46 ms 8400 KB Output is correct
11 Correct 42 ms 7628 KB Output is correct
12 Correct 37 ms 7972 KB Output is correct
13 Correct 50 ms 9172 KB Output is correct
14 Correct 523 ms 69144 KB Output is correct
15 Incorrect 45 ms 9172 KB Output isn't correct
16 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 4 ms 1248 KB Output is correct
3 Correct 4 ms 1248 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -