Submission #520592

#	Time	Username	Problem	Language	Result	Execution time	Memory
520592		N1NT3NDO	Autobahn (COI21_autobahn)	C++17	50 / 100	1089 ms	127456 KiB

autobahn

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, k, x;
map<int, ll> pref, in, out, skok;
map<int, bool> good;
ll ans = -1;
set< int > se;

int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL);
    cin >> n >> k >> x;
    for(int i = 1; i <= n; i++)
    {
        int l, t, r;
        cin >> l >> t >> r;

        se.insert(l);
        se.insert(l + t);
        se.insert(r);
        if (l - x >= 1)
          se.insert(l - x);
        if (l + t - x >= 1)
          se.insert(l + t - x);
        if (r - x >= 1)
          se.insert(r - x);
        in[l]++; out[r]++;
        skok[l + t]++;
        good[l] = 1; good[l + t] = 1; good[r] = 1;
    }

    ll cnt = 0, sum = 0, cur = 0, lst = -1;

    for(const auto &i : se)
    {
        if (cnt >= k && lst != -1) sum += (i - lst - 1)* 1ll * cur;
        cnt += in[i];
        cur += skok[i];
        if (cnt >= k) sum += cur;
        //cout << cnt << ' ' << cur << ' ' << i << endl;
        cnt -= out[i];
        cur -= out[i];
        pref[i] = sum;
        //ans = max(ans, sum);
        lst = i;
    }

    //for(auto u : pref) cout << u.fi << ' ' << u.sd << endl;

    for(const auto &i : se)
    {
        if (!good[i]) continue;
        if (i - x >= 0)
          ans = max(ans, pref[i] - pref[i - x]);
    }
    cout << ans;
}

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