oj.uz

Submission #1002741

# Submission time Handle Problem Language Result Execution time Memory
1002741 2024-06-19T19:07:24 Z mariaclara Autobahn (COI21_autobahn) C++17
0 / 100
 1 ms 456 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define fr first
#define sc second

int n, k, x;
map<int,ll> qtd, val, pref;
set<int> zerar;

ll prefix(int ind) {
    auto ptr = pref.upper_bound(ind);
    if(ptr == pref.begin()) return 0;
    ptr--;
    ll resp = (*ptr).sc + val[(*ptr).fr] * (ind - (*ptr).fr);
    return resp;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> x;

    for(int i = 0, a, b, c; i < n; i++) {
        cin >> a >> c >> b;
        qtd[a]++;
        qtd[b+1]--;
        val[a+c]++;
        val[b+1]--;
        if(qtd.count(a+c) == 0) qtd[a+c] = 0;
        if(val.count(a) == 0) val[a] = 0;
    }

    int at = 0;
    for(auto [ind, a] : qtd) {
        at += a;
        qtd[ind] = at;
        if(at < k) zerar.insert(ind); 
    }

    //cout << "\n";
    at = 0;
    ll p = 0, last_ind = 0, last_val = 0;
    for(auto [ind, a] : val) {
        at += a;
        int at2 = at;
        if(zerar.count(ind)) at2 = 0;
        p += last_val * (ind - last_ind);
        pref[ind] = p + at2;
        val[ind] = at2;
        //cout << ind << " " << p+at2 << " " << at2 << "\n";

        last_ind = ind;
        last_val = at2;
    }

    //cout << "check: " << prefix(67) << " " << prefix(76) << "\n";
    ll ans = 0;
    for(auto [ind, a] : val) {
        ll a1 = prefix(ind) - prefix(ind - x);
        ll a2 = prefix(ind + x - 1) - prefix(ind - 1);
        ans = max({ans, a1, a2});
    }

    cout << ans << "\n";
}

/*
clara
4 1 8
51 9 61
61 7 87
74 2 75
14 2 75
*/

Subtask #1
0 / 20.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
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.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
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 50.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
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -