Submission #149521

#	Time	Username	Problem	Language	Result	Execution time	Memory
149521		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	19 / 100	3108 ms	209688 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct cht {
	vector<ar<int, 2>> v;
	int a[1<<18], b[1<<18], qt;
	void al(int a, int b) {
		v.push_back({a, b});
	}
	void init() {
		for(ar<int, 2> vi : v) {
			while(qt&&vi[0]==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-vi[0])>=(ll)(vi[1]-b[qt-1])*(a[qt-2]-a[qt-1]))
				--qt;
			a[qt]=vi[0];
			b[qt]=vi[1];
			++qt;
		}
	}
	ll qry(ll x, ll y) {
		int lb=0, rb=qt-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			if(a[mb]*x+b[mb]*y>a[mb+1]*x+b[mb+1]*y)
				rb=mb;
			else
				lb=mb+1;
		}
		return a[lb]*x+b[lb]*y;
	}
} ca[19][2], cd[19][2];

int n, k, q[300000];

void Init(vector<int> a, vector<int> d, vector<int> p) {
	n=a.size();
	while(1<<k<n)
		++k;
	iota(q, q+n, 0);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{a[i], p[i]}<ar<int, 2>{a[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			ca[j][q[i]>>j&1].al(a[q[i]], p[q[i]]);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{d[i], p[i]}<ar<int, 2>{d[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			cd[j][q[i]>>j&1].al(d[q[i]], p[q[i]]);
	for(int j=0; j<k; ++j) {
		for(int l : {0, 1}) {
			ca[j][l].init();
			cd[j][l].init();
		}
	}
}

ll BestSquad(int x, int y) {
	ll ans=0;
	for(int i=0; i<k; ++i) {
		ans=max(ans, ca[i][0].qry(x, y)+cd[i][1].qry(x, y));
		ans=max(ans, cd[i][0].qry(x, y)+ca[i][1].qry(x, y));
	}
	return ans;
}

Compilation message (stderr)

squad.cpp: In member function 'void cht::init()':
squad.cpp:16:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while(qt&&vi[0]==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-vi[0])>=(ll)(vi[1]-b[qt-1])*(a[qt-2]-a[qt-1]))
          ~~^~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53