oj.uz

Submission #569961

# Submission time Handle Problem Language Result Execution time Memory
569961 2022-05-28T11:01:06 Z jcelin Autobahn (COI21_autobahn) C++14
100 / 100
 626 ms 252504 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vLL>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 7;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;

ll n, k, x;
gp_hash_table<int, ll> pref, in, out, skok;
gp_hash_table<int, bool> good;
ll ans = -1;
vi vec;
 
void solve(){
    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 and lst != -1) sum += (ll)(i - lst - 1) * (ll)cur;
        cnt += in[i];
        cur += skok[i];
        if(cnt >= k) sum += cur;
        
        cnt -= out[i];
        cur -= out[i];
        pref[i] = sum;
        lst = i;
    }
 
    for(const auto &i : vec){
        if(!good[i]) continue;
        if(i - x >= 0) ans = max(ans, pref[i] - pref[i - x]);
    }
    cout << ans << "\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 623 ms 249828 KB Output is correct
22 Correct 598 ms 252488 KB Output is correct
23 Correct 626 ms 252504 KB Output is correct
24 Correct 407 ms 140384 KB Output is correct
25 Correct 403 ms 140512 KB Output is correct
26 Correct 405 ms 140352 KB Output is correct
27 Correct 318 ms 140004 KB Output is correct
28 Correct 360 ms 140076 KB Output is correct
29 Correct 338 ms 140144 KB Output is correct