oj.uz

Submission #149632

# Submission time Handle Problem Language Result Execution time Memory
149632 2019-09-01T06:52:31 Z 还没编好(#3801, cauchysheep, fjzzq2002, apiad) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 2634 ms 478164 KB 
#pragma GCC optimize("-Ofast","-funroll-all-loops","-ffast-math")
#include "squad.h"
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 4444444
typedef pair<int,int> pll;
ll operator * (pll a,pll b)
{
	return a.fi*(ll)b.se-(ll)a.se*b.fi;
}
pll operator - (pll a,pll b)
{
	return pll(a.fi-b.fi,a.se-b.se);
}
pll operator + (pll a,pll b)
{
	return pll(a.fi+b.fi,a.se+b.se);
}
void convex_hull(vector<pll>& p)
{
	stable_sort(p.begin(),p.end());
	p.erase(unique(p.begin(),p.end()),p.end());
	if(p.size()<=2) return;
	vector<pll> h;
	for(int r=0;r<2;++r)
	{
		int l=h.size();
		for(auto x:p)
		{
			while((int)h.size()>l+1&&
			(h[h.size()-1]-h[h.size()-2])
			*(x-h[h.size()-2])<=0) h.pop_back();
			h.pb(x);
		}
		h.pop_back();
		reverse(p.begin(),p.end());
	}
	p=h;
}
vector<pll> su(const vector<pll>& aa,const vector<pll>& bb)
{
//	vector<pll> g;
//	for(auto x:aa)
//	for(auto y:bb) g.pb(y+x);
//	g=convex_hull(g);
//	return g;
	static pll ans[SZ],a[SZ],b[SZ];
	int top,top1=aa.size(),top2=bb.size();
	for(int i=1;i<top1;++i) a[i]=aa[i]-aa[i-1];
	for(int i=1;i<top2;++i) b[i]=bb[i]-bb[i-1];
	a[top1]=aa[0]-aa[top1-1];
	b[top2]=bb[0]-bb[top2-1];
    //for(int i=1;i<=top1;i++)a[i]=stack1[i+1]-stack1[i];
    //for(int i=1;i<=top2;i++)b[i]=stack2[i+1]-stack2[i];
    ans[top=1]=aa[0]+bb[0];
    int now1=1,now2=1;
    while(now1<=top1&&now2<=top2)
		top++,ans[top]=ans[top-1]+
		((a[now1]*b[now2])>=0?a[now1++]:b[now2++]);
    while(now1<=top1)top++,ans[top]=ans[top-1]+a[now1++];
    while(now2<=top2)top++,ans[top]=ans[top-1]+b[now2++];
    top--;
	vector<pll> oo(top);
	for(int i=0;i<top;++i) oo[i]=(ans[i+1]);
	return oo;
}
int n,a[SZ],d[SZ],p[SZ];
vector<pll> op;
vector<pll> oa[SZ],ob[SZ];
void go(int l,int r,int i=1)
{
	if(l>=r)
	{
		for(int t=l;t<=r;++t)
			oa[i].pb(pll(a[t],p[t])),
			ob[i].pb(pll(d[t],p[t]));
		return;
	}
	int m=(l+r)>>1;
	go(l,m,i*2); go(m+1,r,i*2+1);
	vector<pll> &A=oa[i*2],&B=ob[i*2],&C=oa[i*2+1],&D=ob[i*2+1];
//	vector<pll> A(m-l+1),B(m-l+1),C(r-m),D(r-m);
//	for(int i=l;i<=m;++i)
//		A[i-l]=(pll(a[i],p[i])),
//		B[i-l]=(pll(d[i],p[i]));
//	for(int i=m+1;i<=r;++i)
//		C[i-m-1]=(pll(a[i],p[i])),
//		D[i-m-1]=(pll(d[i],p[i]));
	#define CH(w) convex_hull(w)
	CH(A);CH(B);CH(C);CH(D);
//	cout<<A.size()<<"w"<<B.size()<<"w"<<C.size()<<"w"<<D.size()<<"\n";
	for(auto t:su(A,D)) op.pb(t);
	for(auto t:su(B,C)) op.pb(t);
	for(auto t:C) A.pb(t);
	for(auto t:D) B.pb(t);
	swap(A,oa[i]);
	swap(B,ob[i]);
}
struct fs
{
ll a,b;
fs() {}
fs(ll p,ll q)
{
	if(q==0) a=-4e9,b=1;
	else
	{
		if(q<0) q=-q,p=-p;
		a=p,b=q;
	}
}
};
bool operator < (fs a,fs b)
{
	return a.a*b.b<b.a*a.b;
}
vector<pair<fs,pll>> sb;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n=A.size();
	assert(n<=300000);
	for(int i=0;i<n;++i)
		a[i]=A[i],d[i]=D[i],p[i]=P[i];
	go(0,n-1);
//	for(auto u:op) cout<<u.fi<<","<<u.se<<"!";
//	cout<<"\n";
	convex_hull(op);
//	for(auto w:op)
//		cout<<w.fi<<","<<w.se<<" ";
//	cout<<"\n";
	for(int j=0;j<op.size();++j)
	{
		pll P=op[j],Q=op[(j+1)%op.size()];
		pll t=P;
		if(t.fi<=Q.fi&&t.se<=Q.se) t=Q;
		sb.pb(mp(fs(Q.se-P.se,Q.fi-P.fi),t));
	}
	sort(sb.begin(),sb.end());
}

long long BestSquad(int X, int Y){
	auto w=lower_bound(sb.begin(),sb.end(),mp(fs(-X,Y),pll(0,0)));
	for(int j=1;j<=16&&w!=sb.begin();++j)
		--w;
	ll mx=0;
	for(int j=0;j<16&&j<sb.size();++j)
		mx=max(mx,sb[j].se.fi*(ll)X+sb[j].se.se*(ll)Y);
//	for(int w=0,j=sb.size()-1;w<5&&w<sb.size();++w,--j)
//		mx=max(mx,sb[j].se.fi*(ll)X+sb[j].se.se*(ll)Y);
	for(int j=1;j<=32&&w!=sb.end();++j)
	{
		mx=max(mx,X*(ll)w->se.fi+Y*(ll)w->se.se);
		++w;
	}
	return mx;
}
#ifdef LOCAL
#include "grader.cpp"
#endif

Compilation message

squad.cpp: In function 'void Init(std::vector<int>, std::vector<int>, std::vector<int>)':
squad.cpp:160:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<op.size();++j)
              ~^~~~~~~~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:175:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<16&&j<sb.size();++j)
                    ~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 209144 KB Output is correct
2 Correct 140 ms 209528 KB Output is correct
3 Correct 1389 ms 291996 KB Output is correct
4 Correct 1322 ms 291868 KB Output is correct
5 Correct 251 ms 223704 KB Output is correct
6 Correct 2634 ms 478164 KB Output is correct
7 Correct 2598 ms 478164 KB Output is correct
8 Correct 2570 ms 478164 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 209144 KB Output is correct
2 Correct 144 ms 209656 KB Output is correct
3 Correct 1172 ms 280352 KB Output is correct
4 Correct 1227 ms 280348 KB Output is correct
5 Correct 204 ms 214760 KB Output is correct
6 Correct 1976 ms 374492 KB Output is correct
7 Correct 2031 ms 374556 KB Output is correct
8 Correct 2089 ms 374488 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 209144 KB Output is correct
2 Correct 140 ms 209528 KB Output is correct
3 Correct 1389 ms 291996 KB Output is correct
4 Correct 1322 ms 291868 KB Output is correct
5 Correct 251 ms 223704 KB Output is correct
6 Correct 2634 ms 478164 KB Output is correct
7 Correct 2598 ms 478164 KB Output is correct
8 Correct 2570 ms 478164 KB Output is correct
9 Correct 138 ms 209144 KB Output is correct
10 Correct 144 ms 209656 KB Output is correct
11 Correct 1172 ms 280352 KB Output is correct
12 Correct 1227 ms 280348 KB Output is correct
13 Correct 204 ms 214760 KB Output is correct
14 Correct 1976 ms 374492 KB Output is correct
15 Correct 2031 ms 374556 KB Output is correct
16 Correct 2089 ms 374488 KB Output is correct
17 Correct 206 ms 211704 KB Output is correct
18 Correct 138 ms 210036 KB Output is correct
19 Correct 1505 ms 291996 KB Output is correct
20 Correct 1514 ms 292000 KB Output is correct
21 Incorrect 230 ms 218136 KB Output isn't correct
22 Halted 0 ms 0 KB -