Submission #96135

#	Time	Username	Problem	Language	Result	Execution time	Memory
96135		kig9981	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	440 KiB

aliens

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct lichao
{
	int l, r, k;
	long long A, B;
	lichao() : l(0), r(0), k(0), A(0), B(0x7fffffffffffffffLL) {}
};

vector<lichao> tree;
vector<pair<int,int>> P;

int get_sign(long long a)
{
	return a<0 ? -1:a>0;
}

void update(long long A, long long B, int k, int p=1, int s=0, int e=1000000)
{
	int m=(s+e)>>1, &pk=tree[p].k;
	long long &pA=tree[p].A, &pB=tree[p].B;
	if(pA*m+pB>A*m+B) {
		swap(A,pA);
		swap(B,pB);
		swap(k,pk);
	}
	if(pA*s+pB<=A*s+B && pA*e+pB<=A*e+B) return;
	if(get_sign(pA*s+pB-(A*s+B))*get_sign(pA*m+pB-(A*m+B))<=0) {
		if(tree[p].l==0) tree[p].l=tree.size(), tree.push_back(lichao());
		update(A,B,k,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=tree.size(), tree.push_back(lichao());
		update(A,B,k,tree[p].r,m+1,e);
	}
}

pair<long long,int> query(int x, int p=1, int s=0, int e=1000000)
{
	int m=(s+e)>>1;
	if(p==0) return {0x7fffffffffffffffLL,0x7fffffff};
	return min(make_pair(tree[p].A*x+tree[p].B,tree[p].k),x<=m ? query(x,tree[p].l,s,m):query(x,tree[p].r,m+1,e));
}

pair<long long,int> solve(long long l)
{
	int N=P.size()-1;
	pair<long long,int> ret;
	tree.resize(2);
	tree[1]=lichao();
	update(-2LL*P[0].first,1LL*P[0].first*P[0].first,0);
	for(int i=0;i<N;i++) {
		long long temp;
		ret=query(P[i].second);
		ret.first+=1LL*P[i].second*P[i].second+l;
		temp=max(P[i].second-P[i+1].first,0);
		update(-2LL*P[i+1].first,1LL*P[i+1].first*P[i+1].first+ret.first-temp*temp,++ret.second);
	}
	return ret;
}

long long take_photos(int N, int M, int K, vector<int> R, vector<int> C)
{
	int i, j=0;
	long long s=0, e=1e13;
	P.resize(N);
	for(i=0;i<N;i++) {
		if(R[i]>C[i]) swap(R[i],C[i]);
		P[i]={R[i],-C[i]};
	}
	sort(P.begin(),P.end());
	for(i=0;i<N;i++) {
		P[i].second=-P[i].second+1;
		if(j==0 || P[j-1].second<P[i].second) {
			P[j++]=P[i];
		}
	}
	P.resize(j);
	P.emplace_back(0x7fffffff,0x7fffffff);
	while(s<=e) {
		long long m=(s+e)>>1;
		if(solve(m).second>K) s=m+1;
		else e=m-1;
	}
	return solve(s).first-1LL*s*K;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40