oj.uz

Submission #736307

# Submission time Handle Problem Language Result Execution time Memory
736307 2023-05-05T12:23:02 Z definitelynotmee Strange Device (APIO19_strange_device) C++
10 / 100
 482 ms 32636 KB 
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const ll MAXN = 1e18+10;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, a, b;
    cin >> n >> a >> b;

    if(a%(b+1) == 0)
        a/=b+1;

    bool beeg = (MAXN+b-1)/b < a;

    vector<pll> v(n);

    ll resp = 0;
    vector<pll> interval;

    for(auto& [l, r] : v){
        cin >> l >> r;
        if(beeg){
            resp+=r-l+1;
        } else {
            if(r-l >= a*b){
                cout << a*b << '\n';
                return 0;
            }
            ll tl = l%(a*b), tr = r%(a*b);

            if(tl <= tr){
                interval.push_back({tl,tr});
            } else {
                interval.push_back({tl,a*b-1});
                interval.push_back({0,tr});
            }
        }
    }

    if(beeg){
        cout << resp << '\n';
        return 0;
    }

    sort(all(interval));

    ll counted = -1;

    for(auto [l,r] : interval){
        if(counted < l){
            resp+=r-l+1;
            counted = r;
        } else {
            resp+=r-counted;
            counted = r;
        }
    }
    
    cout << resp << '\n';

    return 0;

}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto& [l, r] : v){
      |               ^
strange_device.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [l,r] : interval){
      |              ^

Subtask #1
0 / 10.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 452 ms 32476 KB Output is correct
3 Correct 402 ms 32492 KB Output is correct
4 Correct 434 ms 32464 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 452 ms 32476 KB Output is correct
3 Correct 402 ms 32492 KB Output is correct
4 Correct 434 ms 32464 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 417 ms 32552 KB Output is correct
7 Correct 392 ms 32528 KB Output is correct
8 Correct 447 ms 32432 KB Output is correct
9 Incorrect 462 ms 32524 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 452 ms 32476 KB Output is correct
3 Correct 402 ms 32492 KB Output is correct
4 Correct 434 ms 32464 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 43 ms 3996 KB Output is correct
7 Correct 46 ms 3980 KB Output is correct
8 Correct 42 ms 4008 KB Output is correct
9 Correct 39 ms 4064 KB Output is correct
10 Correct 41 ms 4000 KB Output is correct
11 Correct 45 ms 4012 KB Output is correct
12 Correct 39 ms 4032 KB Output is correct
13 Correct 44 ms 3968 KB Output is correct
14 Correct 40 ms 4040 KB Output is correct
15 Incorrect 54 ms 4024 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4072 KB Output is correct
3 Correct 42 ms 4036 KB Output is correct
4 Correct 482 ms 32476 KB Output is correct
5 Correct 40 ms 4020 KB Output is correct
6 Correct 44 ms 4048 KB Output is correct
7 Correct 43 ms 4032 KB Output is correct
8 Correct 43 ms 4064 KB Output is correct
9 Correct 45 ms 3984 KB Output is correct
10 Correct 41 ms 4040 KB Output is correct
11 Correct 41 ms 3968 KB Output is correct
12 Correct 40 ms 4120 KB Output is correct
13 Correct 41 ms 4076 KB Output is correct
14 Incorrect 432 ms 32636 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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