oj.uz

Submission #149466

# Submission time Handle Problem Language Result Execution time Memory
149466 2019-09-01T06:32:41 Z 还没编好(#3801, cauchysheep, fjzzq2002, apiad) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 2736 ms 416344 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 1111111
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);
}
vector<pll> 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 p;
	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());
	}
	return 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;
	for(int i=1;i<=top;++i) oo.pb(ans[i]);
	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) 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=-2.01e9,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();
	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";
	op=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<=8&&w!=sb.begin();++j)
		--w;
	ll mx=0;
	for(int j=0;j<6&&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<=16&&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:158: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:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<6&&j<sb.size();++j)
                   ~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 52608 KB Output is correct
2 Correct 43 ms 52984 KB Output is correct
3 Correct 1345 ms 157492 KB Output is correct
4 Correct 1355 ms 157468 KB Output is correct
5 Correct 178 ms 71896 KB Output is correct
6 Correct 2736 ms 416340 KB Output is correct
7 Correct 2643 ms 416344 KB Output is correct
8 Correct 2726 ms 416340 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 52600 KB Output is correct
2 Correct 51 ms 53244 KB Output is correct
3 Correct 1182 ms 141852 KB Output is correct
4 Correct 1133 ms 141852 KB Output is correct
5 Correct 105 ms 59884 KB Output is correct
6 Correct 2056 ms 276824 KB Output is correct
7 Correct 1876 ms 276824 KB Output is correct
8 Correct 2001 ms 276824 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 52608 KB Output is correct
2 Correct 43 ms 52984 KB Output is correct
3 Correct 1345 ms 157492 KB Output is correct
4 Correct 1355 ms 157468 KB Output is correct
5 Correct 178 ms 71896 KB Output is correct
6 Correct 2736 ms 416340 KB Output is correct
7 Correct 2643 ms 416344 KB Output is correct
8 Correct 2726 ms 416340 KB Output is correct
9 Correct 43 ms 52600 KB Output is correct
10 Correct 51 ms 53244 KB Output is correct
11 Correct 1182 ms 141852 KB Output is correct
12 Correct 1133 ms 141852 KB Output is correct
13 Correct 105 ms 59884 KB Output is correct
14 Correct 2056 ms 276824 KB Output is correct
15 Correct 1876 ms 276824 KB Output is correct
16 Correct 2001 ms 276824 KB Output is correct
17 Correct 117 ms 55032 KB Output is correct
18 Correct 54 ms 53620 KB Output is correct
19 Correct 1508 ms 157468 KB Output is correct
20 Correct 1518 ms 157468 KB Output is correct
21 Incorrect 131 ms 64484 KB Output isn't correct
22 Halted 0 ms 0 KB -