oj.uz

Submission #150080

# Submission time Handle Problem Language Result Execution time Memory
150080 2019-09-01T07:41:08 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Organizing the Best Squad (FXCUP4_squad) C++17
28 / 100
 1008 ms 90708 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[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({P[i], A[i], i, 1});
		w.push_back({P[i], D[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){
	swap(X, 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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 8 ms 3072 KB Output is correct
3 Correct 329 ms 88456 KB Output is correct
4 Correct 342 ms 88472 KB Output is correct
5 Incorrect 26 ms 8572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 11 ms 3712 KB Output is correct
3 Correct 561 ms 90700 KB Output is correct
4 Correct 549 ms 90708 KB Output is correct
5 Correct 32 ms 6644 KB Output is correct
6 Correct 969 ms 90452 KB Output is correct
7 Correct 1008 ms 90692 KB Output is correct
8 Correct 912 ms 90692 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2944 KB Output is correct
2 Correct 8 ms 3072 KB Output is correct
3 Correct 329 ms 88456 KB Output is correct
4 Correct 342 ms 88472 KB Output is correct
5 Incorrect 26 ms 8572 KB Output isn't correct
6 Halted 0 ms 0 KB -