oj.uz

Submission #520587

# Submission time Handle Problem Language Result Execution time Memory
520587 2022-01-30T09:38:00 Z N1NT3NDO Autobahn (COI21_autobahn) C++14
0 / 100
 1 ms 332 KB 
#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;

const int N = (int)1e5 + 500;
int n, k, x;
map<int, ll> pref, in, out, skok;
map<int, bool> good;
ll ans = -1;
map< int, vector<int>> m;
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(auto i : se)
    {
        if (cnt >= k && lst != -1) sum += (i - lst - 1) * 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(auto i : se)
    {
        if (!good[i]) continue;
        if (i - x >= 1)
          ans = max(ans, pref[i] - pref[i - x]);
    }
    cout << ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Halted 0 ms 0 KB -