oj.uz

Submission #520571

# Submission time Handle Problem Language Result Execution time Memory
520571 2022-01-30T09:17:11 Z N1NT3NDO Autobahn (COI21_autobahn) C++14
50 / 100
 2 ms 716 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;
int skok[N], ans = -1, in[N], out[N], pref[N];

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;
        in[l]++; out[r]++;
        skok[l + t]++;
    }

    int cnt = 0, sum = 0, cur = 0;
    for(int i = 1; i < N; i++)
    {
        cnt += in[i];
        cur += skok[i];
        //cout << cnt << ' ' << cur << ' ' << i << endl;
        if (cnt >= k) sum += cur;
        cnt -= out[i];
        cur -= out[i];
        pref[i] = sum;
        //ans = max(ans, sum);
    }

    for(int i = x; i < N; i++) ans = max(ans, pref[i] - pref[i - x]);

    cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 624 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 716 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 624 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 2 ms 716 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 716 KB Output is correct
21 Runtime error 1 ms 460 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -