Submission #149669

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

squad

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

#define ll long long
#define ar array

struct cht {
	int a[1<<18], b[1<<18], qt;
	ar<int, 2> l[1<<18];
	void al(int c, int d) {
		while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
			--qt;
		a[qt]=c;
		b[qt]=d;
		++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;
	}
	void cl() {
		for(int i=0; i<qt; ++i) {
			;
		}
	}
} c[76];

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)
			c[j*4+(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)
			c[j*4+2+(q[i]>>j&1)].al(d[q[i]], p[q[i]]);
	for(int i=0; i<k*4; ++i) {
		c[i].cl();
	}
}

ll BestSquad(int x, int y) {
	ll ans=0, d[k*4];
	for(int i=0; i<k*4; ++i)
		d[i]=c[i].qry(x, y);
	//frucktional cascading
	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));
		ans=max(ans, d[i*4]+d[i*4+3]);
		ans=max(ans, d[i*4+1]+d[i*4+2]);
	}
	return ans;
}

Compilation message (stderr)

squad.cpp: In member function 'void cht::al(int, int)':
squad.cpp:12:11: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(qt&&c==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-c)>=(ll)(d-b[qt-1])*(a[qt-2]-a[qt-1]))
         ~~^~~~~~~~~~~~

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