oj.uz

Submission #529430

# Submission time Handle Problem Language Result Execution time Memory
529430 2022-02-23T02:12:25 Z jiahng Autobahn (COI21_autobahn) C++14
100 / 100
 742 ms 64452 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MOD 1000000007
#define maxn 2000010
//~ #define getchar_unlocked _getchar_nolock

int N,K,X,l,r,t;

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int32_t main() {
    fast;
    N = readInt(); K = readInt(); X = readInt();
	vpi v; vi vect;
    FOR(i,1,N){
		l = readInt(); t = readInt(); r = readInt();
		v.pb(pi(l, 0));
		v.pb(pi(l+t,1));
		v.pb(pi(r+1, 2));
		v.pb(pi(l-X,3)); v.pb(pi(r-X,3));
		v.pb(pi(l-1,3)); v.pb(pi(r-1,3));
		v.pb(pi(l+X-1,3)); v.pb(pi(r+X-1,3));
		v.pb(pi(r,3));
		vect.pb(l); vect.pb(r); vect.pb(l-X+1); vect.pb(r-X+1);
	}
	sort(all(v));
	int ppl_num = 0, charge_num = 0, cur_ss = 0;
	unordered_map <int,int> ss;
	FOR(i,0,v.size()-1){
		int pos = v[i].f;
		while (i < (int)v.size() && v[i].f == pos){
			if (v[i].s == 0) ppl_num++;
			else if (v[i].s == 1) charge_num++;
			else if (v[i].s == 2){
				ppl_num--; charge_num--;
			}
			i++;
		}
		i--;
		if (ppl_num >= K){
			ss[pos] = cur_ss + charge_num;
			cur_ss += charge_num * (v[i+1].f - v[i].f);
		}else ss[pos] = cur_ss;
	}
	int ans = 0;
	aFOR(i,vect){
		ans = max(ans, ss[i+X-1] - ss[i-1]);
	}
	cout << ans;
	
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 2 ms 652 KB Output is correct
17 Correct 2 ms 656 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 652 KB Output is correct
15 Correct 2 ms 652 KB Output is correct
16 Correct 2 ms 652 KB Output is correct
17 Correct 2 ms 656 KB Output is correct
18 Correct 2 ms 652 KB Output is correct
19 Correct 2 ms 652 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 663 ms 61712 KB Output is correct
22 Correct 689 ms 64436 KB Output is correct
23 Correct 677 ms 64388 KB Output is correct
24 Correct 742 ms 64452 KB Output is correct
25 Correct 734 ms 64412 KB Output is correct
26 Correct 702 ms 64396 KB Output is correct
27 Correct 664 ms 64448 KB Output is correct
28 Correct 636 ms 64448 KB Output is correct
29 Correct 715 ms 64344 KB Output is correct