Submission #172712

#	Time	Username	Problem	Language	Result	Execution time	Memory
172712		red1108	Aliens (IOI16_aliens)	C++17	100 / 100	202 ms	11752 KiB

aliens

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define pb push_back
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 1e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cout << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cout << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cout << endl;}

ll dp[101010];
vector<pll> tmp, p;
int cur=0;
struct Line{
	ll a, b;
	int cnt;
	Line(){}
	Line(ll aa, ll bb, int cc){a=aa;b=bb;cnt=cc;}
};
vector<Line> line;
double cross(Line A, Line B){
	return (double)(B.b-A.b)/(double)(A.a-B.a);
}
pll get(ll x){
	while(cur+1<line.size()&&cross(line[cur],line[cur+1])<=(double)x) cur++;
	//printf("why?? %d\n", cur);
	//for(auto i:line) printf("deug (%lld,%lld)\n", i.a,i.b);
	if(cur>=line.size()) return pll(0,0);
	return pll(line[cur].a*x+line[cur].b,line[cur].cnt);
}
void add(Line nl){
	while(line.size()>=2&&cross(line[line.size()-2],line[line.size()-1])>=cross(line[line.size()-2],nl)) line.pop_back();
	line.push_back(nl);
}
int get_take(ll c){
	//dp초기화
	cur=0;
	line.clear();
	add(Line(-2*(p[1].fi-1),c+(p[1].fi-1)*(p[1].fi-1),1));
	pll t;
	for(int i=1;i<(int)p.size();i++){
		if(i>1){
			if(p[i].fi<=p[i-1].se) add(Line(-2*(p[i].fi-1),c+t.fi+(p[i].fi-1)*(p[i].fi-1) - (p[i-1].se-p[i].fi+1)*(p[i-1].se-p[i].fi+1),t.se+1));
			else add(Line(-2*(p[i].fi-1),c+t.fi+(p[i].fi-1)*(p[i].fi-1),t.se+1));
		}
		t = get(p[i].se);
		t.fi+=p[i].se*p[i].se;
		dp[i]=t.fi;
	}
	return (int)t.se;
}
ll take_photos(int n, int m, int k, vector<int>x, vector<int>y){
	k=min(n,k);
	for(int i=0;i<n;i++){
		if(x[i]>y[i]) swap(x[i], y[i]);
		tmp.pb({x[i],y[i]});
	}
	sort(tmp.begin(), tmp.end(), [](pii a, pii b){if(a.se==b.se) return a.fi>b.fi;return a.se<b.se;});
	p.pb({-1,-1});
	for(auto i:tmp){
		while(!p.empty()&&p[p.size()-1].fi>=i.fi) p.pop_back();
		p.pb(i);
	}
	k=min(k,(int)p.size()-1);
	ll s = 0,e=(ll)m*m;
	ll l=-1,r=e+1,ly,ry;
	while(s<=e){
		ll mid = (s+e)/2;
		int num = get_take(mid);
		if(num==k) return dp[p.size()-1]-mid*k;
		if(num>k){
			s = mid+1;
			if(r>num) r=num,ry=dp[p.size()-1]-mid*num;
		}
		if(num<k){
			e = mid-1;
			if(l<num) l=num,ly=dp[p.size()-1]-mid*num;
		}
	}
	if(r==(ll)m*m+1) return ly;
	if(l==-1) return ry;
	return ry+(ly-ry)/(r-l)*(r-k);
}

Compilation message (stderr)

aliens.cpp: In function 'pll get(ll)':
aliens.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(cur+1<line.size()&&cross(line[cur],line[cur+1])<=(double)x) cur++;
        ~~~~~^~~~~~~~~~~~
aliens.cpp:43:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cur>=line.size()) return pll(0,0);
     ~~~^~~~~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:97:30: warning: 'ry' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ry+(ly-ry)/(r-l)*(r-k);
                              ^

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