oj.uz

Submission #150887

# Submission time Handle Problem Language Result Execution time Memory
150887 2019-09-01T09:54:54 Z gs14004 Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1210 ms 87792 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
 
#include "squad.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
const int MAXN = 300005;
 
struct pi{
	int first, second, idx, cnt;
	bool operator<(const pi &q)const{
		return make_pair(first, second) < make_pair(q.first, q.second);
	}
};
 
lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
 
struct convex_hull{
	vector<pi> V;
	void init(vector<pi> inp){
		for(auto &i : inp){
			while(sz(V) >= 2 && ccw(V[sz(V) - 2], V.back(), i) > 0) V.pop_back();
			V.push_back(i);
		}
	}
	pair<lint, int> get(int x, int y){
		lint cur = -5e18;
		int cnt = 0;
		int pos = -1;
		if(sz(V)){
			int s = 0, e = sz(V) - 1;
			while(s != e){
				int m = (s+e)/2;
				lint qr1 = 1ll * V[m].first * x + 1ll * V[m].second * y;
				lint qr2 = 1ll * V[m+1].first * x + 1ll * V[m+1].second * y;
				if(qr1 < qr2) s = m + 1;
				else e = m;
			}
			for(int i=s; i<sz(V) && i<s+2; i++){
				lint qr = 1ll * V[i].first * x + 1ll * V[i].second * y;
				if(qr > cur){
					cur = qr;
					cnt = 0;
					pos = V[i].idx;
				}
				if(qr == cur) cnt += V[i].cnt;
			}
		}
		if(cnt >= 2) pos = -1;
		return make_pair(cur, pos);
	}
}X, Y, FUCKX[MAXN], FUCKY[MAXN];
 
int N;
vector<pi> v, w;
 
vector<pi> norm(vector<pi> v){
	sort(v.begin(), v.end());
	vector<pi> w;
	for(int i=0; i<sz(v); ){
		int e = i;
		while(e < sz(v) && make_pair(v[i].first, v[i].second) == make_pair(v[e].first, v[e].second)) e++;
		w.push_back({v[i].first, v[i].second, v[i].idx, e - i});
		i = e;
	}
	return w;
}
 
int revX[MAXN], revY[MAXN];
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = sz(A);
	for(int i=0; i<N; i++){
		v.push_back({A[i], P[i], i, 1});
		w.push_back({D[i], P[i], i, 1});
	}
	v = norm(v);
	w = norm(w);
	X.init(v);
	Y.init(w);
	for(int i=0; i<sz(v); i++) revX[v[i].idx] = i;
	for(int i=0; i<sz(w); i++) revY[w[i].idx] = i;
	for(int i=0; i<sz(X.V); i++){
		int l = X.V[max(i - 1, 0)].idx;
		int r = X.V[min(i + 1, sz(X.V) - 1)].idx;
		l = revX[l];
		r = revX[r];
		vector<pi> fuck;
		for(int j=l; j<=r; j++){
			if(v[j].idx != X.V[i].idx) fuck.push_back(v[j]);
		}
		FUCKX[X.V[i].idx].init(fuck);
	}
	for(int i=0; i<sz(Y.V); i++){
		int l = Y.V[max(i - 1, 0)].idx;
		int r = Y.V[min(i + 1, sz(Y.V) - 1)].idx;
		l = revY[l];
		r = revY[r];
		vector<pi> fuck;
		for(int j=l; j<=r; j++){
			if(w[j].idx != Y.V[i].idx) fuck.push_back(w[j]);
		}
		FUCKY[Y.V[i].idx].init(fuck);
	}
}
 
long long BestSquad(int sex, int sey){
	auto qr1 = X.get(sex, sey);
	auto qr2 = Y.get(sex, sey);
	if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
	lint ret = -5e18;
	ret = max(ret, qr1.first + FUCKY[qr1.second].get(sex, sey).first);
	ret = max(ret, qr2.first + FUCKX[qr2.second].get(sex, sey).first);
	return ret;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14584 KB Output is correct
2 Correct 17 ms 14584 KB Output is correct
3 Correct 355 ms 57228 KB Output is correct
4 Correct 356 ms 59228 KB Output is correct
5 Correct 47 ms 18816 KB Output is correct
6 Correct 740 ms 79496 KB Output is correct
7 Correct 650 ms 79388 KB Output is correct
8 Correct 695 ms 79644 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14456 KB Output is correct
2 Correct 21 ms 14968 KB Output is correct
3 Correct 716 ms 66552 KB Output is correct
4 Correct 731 ms 69416 KB Output is correct
5 Correct 44 ms 17524 KB Output is correct
6 Correct 972 ms 85364 KB Output is correct
7 Correct 924 ms 85352 KB Output is correct
8 Correct 898 ms 85272 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14584 KB Output is correct
2 Correct 17 ms 14584 KB Output is correct
3 Correct 355 ms 57228 KB Output is correct
4 Correct 356 ms 59228 KB Output is correct
5 Correct 47 ms 18816 KB Output is correct
6 Correct 740 ms 79496 KB Output is correct
7 Correct 650 ms 79388 KB Output is correct
8 Correct 695 ms 79644 KB Output is correct
9 Correct 16 ms 14456 KB Output is correct
10 Correct 21 ms 14968 KB Output is correct
11 Correct 716 ms 66552 KB Output is correct
12 Correct 731 ms 69416 KB Output is correct
13 Correct 44 ms 17524 KB Output is correct
14 Correct 972 ms 85364 KB Output is correct
15 Correct 924 ms 85352 KB Output is correct
16 Correct 898 ms 85272 KB Output is correct
17 Correct 92 ms 19412 KB Output is correct
18 Correct 20 ms 14972 KB Output is correct
19 Correct 550 ms 67356 KB Output is correct
20 Correct 543 ms 67452 KB Output is correct
21 Correct 53 ms 18016 KB Output is correct
22 Correct 1172 ms 87792 KB Output is correct
23 Correct 1210 ms 87572 KB Output is correct
24 Correct 1179 ms 87752 KB Output is correct