oj.uz

Submission #149249

# Submission time Handle Problem Language Result Execution time Memory
149249 2019-09-01T06:03:35 Z 还没编好(#3801, cauchysheep, fjzzq2002, apiad) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 416340 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());
	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]);
}
vector<pair<ld,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(int j=0;j<op.size();++j)
	{
		pll P=op[j],Q=op[(j+1)%op.size()];
		sb.pb(mp((Q.se-P.se)/ld(Q.fi-P.fi),P));
		sb.pb(mp((Q.se-P.se)/ld(Q.fi-P.fi),Q));
	}
	sort(sb.begin(),sb.end());
}

long long BestSquad(int X, int Y){
	auto w=lower_bound(sb.begin(),sb.end(),mp(-X/ld(Y),pll(0,0)));
	for(int j=1;j<=8&&w!=sb.begin();++j)
		--w;
	ll mx=0;
	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:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<op.size();++j)
              ~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 52608 KB Output is correct
2 Correct 40 ms 52992 KB Output is correct
3 Correct 1368 ms 157468 KB Output is correct
4 Correct 1402 ms 157468 KB Output is correct
5 Correct 177 ms 71896 KB Output is correct
6 Correct 2801 ms 416340 KB Output is correct
7 Correct 2940 ms 416340 KB Output is correct
8 Correct 2735 ms 416216 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 52600 KB Output is correct
2 Correct 48 ms 53108 KB Output is correct
3 Correct 1133 ms 141852 KB Output is correct
4 Correct 1193 ms 141856 KB Output is correct
5 Correct 109 ms 59884 KB Output is correct
6 Correct 2114 ms 276824 KB Output is correct
7 Correct 2330 ms 276824 KB Output is correct
8 Correct 2089 ms 276824 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 52608 KB Output is correct
2 Correct 40 ms 52992 KB Output is correct
3 Correct 1368 ms 157468 KB Output is correct
4 Correct 1402 ms 157468 KB Output is correct
5 Correct 177 ms 71896 KB Output is correct
6 Correct 2801 ms 416340 KB Output is correct
7 Correct 2940 ms 416340 KB Output is correct
8 Correct 2735 ms 416216 KB Output is correct
9 Correct 42 ms 52600 KB Output is correct
10 Correct 48 ms 53108 KB Output is correct
11 Correct 1133 ms 141852 KB Output is correct
12 Correct 1193 ms 141856 KB Output is correct
13 Correct 109 ms 59884 KB Output is correct
14 Correct 2114 ms 276824 KB Output is correct
15 Correct 2330 ms 276824 KB Output is correct
16 Correct 2089 ms 276824 KB Output is correct
17 Correct 114 ms 55160 KB Output is correct
18 Correct 57 ms 53620 KB Output is correct
19 Correct 1567 ms 157468 KB Output is correct
20 Correct 1528 ms 157492 KB Output is correct
21 Correct 148 ms 64484 KB Output is correct
22 Execution timed out 3109 ms 416340 KB Time limit exceeded
23 Halted 0 ms 0 KB -