Submission #539370

#	Time	Username	Problem	Language	Result	Execution time	Memory
539370		new_acc	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	340 KiB

aliens

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int M=1e6+10;
const int N=1e5+10;
const int INFi=1e9;
const ll INFl=1e12;
int jump[N][18],t[N],mini[M],pot[N],l;
pair<ll,int> dp[N];
int kw[N];
ll res=INFl;
bitset<N>vis;
bool diag(int a,int b){
	return a>=b;
}
int minv(int a,int b){
	int dl=b-a+1;
	return min(jump[b][pot[dl]],jump[a+(1<<pot[dl])-1][pot[dl]]);
}
ll cnt(int i,int j){
	int mm=minv(i+1,j),bok=t[j]-mm+1,g=t[j]-bok+1;
	if(g>t[i]) return dp[i].fi+(ll)(bok)*(ll)(bok);
	if(kw[i]<(t[i]-g+1)) return INFl;
	return dp[i].fi+(ll)(bok)*(ll)(bok)-(ll)(t[i]-g+1)*(ll)(t[i]-g+1);
}
int bs(int a,int b,int pocz,int kon){
	int sr,res=kon+1;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		ll val1=cnt(a,sr),val2=cnt(b,sr);
		if(val1<val2 or (val1==val2 and dp[a].se<=dp[b].se)) res=sr,kon=sr-1;
		else pocz=sr+1;
	}
	return res;
}
bool check(ll c,int k){
	set<int> curr;
	set<pair<int,int> >act;
	curr.insert(1);
	dp[1]={((ll)t[1]-jump[1][0]+1)*(ll)(t[1]-jump[1][0]+1)+(ll)c,1};
	kw[1]=t[1]-jump[1][0]+1;
	act.insert({2,0});
	for(int i=1;i<=l;i++) vis[i]=0;
	while(1){
		auto it=act.begin();
		pair<int,int>v=*it;
		act.erase(it);
		if(v.fi>l) break;
		if(v.se<0){
			v.se*=(-1);
			if(vis[v.se]) continue;
			vis[v.se]=1;
			auto it2=curr.lower_bound(v.se);
			it2--;
			int mn=*it2;
			it2++,it2++;
			if(it2!=curr.end()){
				int wi=*it2;
				act.insert({bs(mn,wi,v.fi,l),-wi});
			}
			it2--;
			curr.erase(it2);
		}else{
			auto it2=curr.end();
			it2--;
			ll val=cnt(*it2,v.fi)+c,val2=minv(1,v.fi);
			if((ll)(t[v.fi]-val2+1)*(ll)(t[v.fi]-val2+1)+c<=val) dp[v.fi]={(ll)(t[v.fi]-val2+1)*(ll)(t[v.fi]-(ll)val2+1)+c,1},kw[v.fi]=(t[v.fi]-val2+1);
			else dp[v.fi]={val,dp[*it2].se+1},kw[v.fi]=t[v.fi]-minv(*it2+1,v.fi)+1;
			act.insert({bs(*it2,v.fi,v.fi+1,l),-v.fi});
			act.insert({v.fi+1,0});
			curr.insert(v.fi);
		}
	}
	if(dp[l].se<=k){
		res=min(res,dp[l].fi-c*(ll)dp[l].se);
		return 1;
	}
	return 0;
}
ll take_photos(int n,int m,int k,vi r,vi c){
	for(int i=1;i<=m;i++) mini[i]=INFi;
	for(int i=1;i<=n;i++){
		r[i-1]++,c[i-1]++;
		if(diag(r[i-1],c[i-1])) mini[r[i-1]]=min(mini[r[i-1]],c[i-1]);
		else mini[c[i-1]]=min(mini[c[i-1]],r[i-1]);
	}
	for(int i=1;i<=m;i++){
		if(mini[i]!=INFi){
			t[++l]=i;
			jump[l][0]=mini[i];
			for(int j=1;l-(1<<j)+1>=1;j++) jump[l][j]=min(jump[l][j-1],jump[l-(1<<(j-1))][j-1]);
		}
	}
	int wsk=0;
	for(int i=1;i<=l;i++){
		pot[i]=wsk;
		if((1<<wsk)==i/2) wsk++;
	}
	ll pocz=0,kon=INFl;
	while(pocz<=kon){
		ll sr=(pocz+kon)>>1;
		if(check(sr,k)) kon=sr-1;
		else pocz=sr+1;
	}
	return res;
}
/*int main(){
	int n,m,k;
	cin>>n>>m>>k;
	vi r,c;
	for(int i=1,a,b;i<=n;i++){
		cin>>a>>b;
		r.push_back(a),c.push_back(b);
	}
	cout<<take_photos(n,m,k,r,c)<<"\n";
}*/

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