oj.uz

Submission #149614

# Submission time Handle Problem Language Result Execution time Memory
149614 2019-09-01T06:50:32 Z 还没编好(#3801, cauchysheep, fjzzq2002, apiad) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 2570 ms 321624 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);
}
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();
	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: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: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 41 ms 52608 KB Output is correct
2 Correct 43 ms 52728 KB Output is correct
3 Correct 1253 ms 135452 KB Output is correct
4 Correct 1224 ms 135452 KB Output is correct
5 Correct 164 ms 67160 KB Output is correct
6 Correct 2385 ms 321620 KB Output is correct
7 Correct 2470 ms 321620 KB Output is correct
8 Correct 2570 ms 321624 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 52608 KB Output is correct
2 Correct 47 ms 53112 KB Output is correct
3 Correct 1175 ms 123816 KB Output is correct
4 Correct 1117 ms 123808 KB Output is correct
5 Correct 104 ms 58216 KB Output is correct
6 Correct 1952 ms 217944 KB Output is correct
7 Correct 1802 ms 217944 KB Output is correct
8 Correct 1901 ms 217992 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 52608 KB Output is correct
2 Correct 43 ms 52728 KB Output is correct
3 Correct 1253 ms 135452 KB Output is correct
4 Correct 1224 ms 135452 KB Output is correct
5 Correct 164 ms 67160 KB Output is correct
6 Correct 2385 ms 321620 KB Output is correct
7 Correct 2470 ms 321620 KB Output is correct
8 Correct 2570 ms 321624 KB Output is correct
9 Correct 42 ms 52608 KB Output is correct
10 Correct 47 ms 53112 KB Output is correct
11 Correct 1175 ms 123816 KB Output is correct
12 Correct 1117 ms 123808 KB Output is correct
13 Correct 104 ms 58216 KB Output is correct
14 Correct 1952 ms 217944 KB Output is correct
15 Correct 1802 ms 217944 KB Output is correct
16 Correct 1901 ms 217992 KB Output is correct
17 Correct 108 ms 55032 KB Output is correct
18 Correct 54 ms 53492 KB Output is correct
19 Correct 1360 ms 135552 KB Output is correct
20 Correct 1454 ms 135452 KB Output is correct
21 Incorrect 167 ms 61540 KB Output isn't correct
22 Halted 0 ms 0 KB -