Submission #520597

#	Time	Username	Problem	Language	Result	Execution time	Memory
520597		N1NT3NDO	Autobahn (COI21_autobahn)	C++14	50 / 100	1097 ms	98012 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()
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("avx2")

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;
unordered_map<int, ll> pref, in, out, skok;
unordered_map<int, bool> good;
ll ans = -1;
vector< int > vec;

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

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

    sort(all(vec));

    vec.erase(unique(all(vec)), vec.end());

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

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

Compilation message (stderr)

autobahn.cpp:12:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
   12 | #pragma GCC optimize("avx2")
      |                            ^
autobahn.cpp:25:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   25 | int main()
      |          ^

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