Submission #96207

#	Time	Username	Problem	Language	Result	Execution time	Memory
96207		kig9981	Aliens (IOI16_aliens)	C++17	4 / 100	5 ms	408 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);
	}
	ret.second=abs(ret.second);
	return ret;
}
 
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C)
{
	int i, j=0, l, r;
	long long s=0, e=1e13, lv, rv;
	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);
	K=min(K,j);
	l=-1; r=j+1;
	while(s<=e) {
		long long m=(s+e)>>1;
		auto c=solve(m);
		if(c.second==K) return c.first-1LL*m*c.second;
		if(c.second>K) {
			s=m+1;
			if(c.second<r) {
				r=c.second;
				rv=c.first-1LL*m*c.second;
			}
		}
		else {
			e=m-1;
			if(c.second>l) {
				l=c.second;
				lv=c.first-1LL*m*c.second;
			}
		}
	}
	return rv+(lv-rv)/(r-l)*(r-K);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:112:30: warning: 'rv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return rv+(lv-rv)/(r-l)*(r-K);
                              ^
aliens.cpp:112:15: warning: 'lv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return rv+(lv-rv)/(r-l)*(r-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