oj.uz

답안 #149935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149935 2019-09-01T07:25:30 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 3000 ms 149460 KB 
#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[20][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<20; 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=19; i>=0; i--){
			if(par[i][n]){
				int R = par[i][n];
				int L = par[0][R];
				lint qr1 = 1ll * x * V[L].first + 1ll * y * V[L].second;
				lint qr2 = 1ll * x * V[R].first + 1ll * y * V[R].second;
				if(qr1 > qr2 && L){
					n = par[i][n];
				}
			}
		}
		int it = 0;
		for(int i=n; i&& it<3; 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;
	sort(v.begin(), v.end());
	for(auto &i : w) i.first *= -1;
	sort(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 5628 KB Output is correct
2 Correct 10 ms 6144 KB Output is correct
3 Correct 430 ms 147224 KB Output is correct
4 Correct 414 ms 147204 KB Output is correct
5 Correct 34 ms 14964 KB Output is correct
6 Correct 367 ms 147204 KB Output is correct
7 Correct 363 ms 147224 KB Output is correct
8 Correct 392 ms 147204 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5632 KB Output is correct
2 Correct 13 ms 6784 KB Output is correct
3 Correct 631 ms 149204 KB Output is correct
4 Correct 617 ms 149460 KB Output is correct
5 Correct 36 ms 11636 KB Output is correct
6 Correct 950 ms 149324 KB Output is correct
7 Correct 957 ms 149336 KB Output is correct
8 Correct 974 ms 149332 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5628 KB Output is correct
2 Correct 10 ms 6144 KB Output is correct
3 Correct 430 ms 147224 KB Output is correct
4 Correct 414 ms 147204 KB Output is correct
5 Correct 34 ms 14964 KB Output is correct
6 Correct 367 ms 147204 KB Output is correct
7 Correct 363 ms 147224 KB Output is correct
8 Correct 392 ms 147204 KB Output is correct
9 Correct 8 ms 5632 KB Output is correct
10 Correct 13 ms 6784 KB Output is correct
11 Correct 631 ms 149204 KB Output is correct
12 Correct 617 ms 149460 KB Output is correct
13 Correct 36 ms 11636 KB Output is correct
14 Correct 950 ms 149324 KB Output is correct
15 Correct 957 ms 149336 KB Output is correct
16 Correct 974 ms 149332 KB Output is correct
17 Correct 118 ms 8056 KB Output is correct
18 Correct 16 ms 7296 KB Output is correct
19 Correct 608 ms 149444 KB Output is correct
20 Correct 640 ms 149444 KB Output is correct
21 Correct 84 ms 11996 KB Output is correct
22 Execution timed out 3106 ms 148676 KB Time limit exceeded
23 Halted 0 ms 0 KB -