oj.uz

답안 #150373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150373 2019-09-01T08:15:05 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 3000 ms 144724 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 query{
	pi V[MAXN];
	int par[19][MAXN], N;
	int revloc[MAXN];
	void init(vector<pi> v){
		memset(revloc, -1, sizeof(revloc));
		N = sz(v);
		vector<int> stk;
		for(int i=0; i<sz(v); i++){
			V[i + 1] = v[i];
		}
		for(int i=1; i<=N; i++){
			while(sz(stk) >= 2 && ccw(V[stk[sz(stk) - 2]], V[stk.back()], V[i]) > 0){
				stk.pop_back();
			}
			if(sz(stk)) par[0][i] = stk.back();
			stk.push_back(i);
		}
		for(int i=1; i<=N; i++) revloc[V[i].idx] = i;
		for(int i=1; i<19; i++){
			for(int j=1; j<=N; j++){
				par[i][j] = par[i-1][par[i-1][j]];
			}
		}
	}
	pair<lint, int> get(int x, int y, int n){
		lint cur = -5e18;
		int cnt = 0;
		int pos = -1;
		for(int i=18; i>=0; i--){
			if(par[i][n] > 1){
				int R = par[i][n];
				int L = par[0][R];
				lint qr1 = 1ll * x * (V[L].first - V[R].first) + 1ll * y * (V[L].second - V[R].second);
				if(qr1 > 0) n = par[i][n];
			}
		}
		int it = 0;
		for(int i=n; i&& it<2; i=par[0][i]){
			it++;
			lint qr = 1ll * x * V[i].first + 1ll * y * V[i].second;
			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);
	}
}XP, YP, XS, YS;

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;
}

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);
	XP.init(v);
	YP.init(w);
	for(auto &i : v) i.first *= -1;
	for(auto &i : w) i.first *= -1;
	reverse(v.begin(), v.end());
	reverse(w.begin(), w.end());
	XS.init(v);
	YS.init(w);
}

long long BestSquad(int X, int Y){
	auto qr1 = XP.get(X, Y, XP.N);
	auto qr2 = YP.get(X, Y, YP.N);
	if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
	lint ret = -5e18;
	ret = max(ret, qr1.first + YP.get(X, Y, YP.revloc[qr1.second] - 1).first);
	ret = max(ret, qr1.first + YS.get(-X, Y, YS.revloc[qr1.second] - 1).first);
	ret = max(ret, qr2.first + XP.get(X, Y, XP.revloc[qr1.second] - 1).first);
	ret = max(ret, qr2.first + XS.get(-X, Y, XS.revloc[qr1.second] - 1).first);
	return ret;
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5632 KB Output is correct
2 Correct 10 ms 6016 KB Output is correct
3 Correct 412 ms 142488 KB Output is correct
4 Correct 376 ms 142488 KB Output is correct
5 Correct 32 ms 14580 KB Output is correct
6 Correct 357 ms 142612 KB Output is correct
7 Correct 363 ms 142232 KB Output is correct
8 Correct 363 ms 142468 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 5504 KB Output is correct
2 Correct 14 ms 6784 KB Output is correct
3 Correct 676 ms 144588 KB Output is correct
4 Correct 672 ms 144708 KB Output is correct
5 Correct 35 ms 11380 KB Output is correct
6 Correct 1332 ms 144636 KB Output is correct
7 Correct 1345 ms 144596 KB Output is correct
8 Correct 1459 ms 144596 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5632 KB Output is correct
2 Correct 10 ms 6016 KB Output is correct
3 Correct 412 ms 142488 KB Output is correct
4 Correct 376 ms 142488 KB Output is correct
5 Correct 32 ms 14580 KB Output is correct
6 Correct 357 ms 142612 KB Output is correct
7 Correct 363 ms 142232 KB Output is correct
8 Correct 363 ms 142468 KB Output is correct
9 Correct 11 ms 5504 KB Output is correct
10 Correct 14 ms 6784 KB Output is correct
11 Correct 676 ms 144588 KB Output is correct
12 Correct 672 ms 144708 KB Output is correct
13 Correct 35 ms 11380 KB Output is correct
14 Correct 1332 ms 144636 KB Output is correct
15 Correct 1345 ms 144596 KB Output is correct
16 Correct 1459 ms 144596 KB Output is correct
17 Correct 122 ms 8056 KB Output is correct
18 Correct 16 ms 7064 KB Output is correct
19 Correct 750 ms 144708 KB Output is correct
20 Correct 631 ms 144724 KB Output is correct
21 Correct 184 ms 11736 KB Output is correct
22 Execution timed out 3106 ms 142476 KB Time limit exceeded
23 Halted 0 ms 0 KB -