Submission #1002717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002717		mariaclara	Autobahn (COI21_autobahn)	C++17	0 / 100	0 ms	348 KiB

autobahn

#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); 
    }

    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;

        last_ind = ind;
        last_val = at2;
    }

    ll ans = 0;
    for(auto [ind, a] : val) {
        ll a1 = prefix(ind) - prefix(ind - x - 1);
        ll a2 = prefix(ind + x - 1) - prefix(ind - 1);
        ans = max({ans, a1, a2});
    }

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50