Seletiva IOI 2015

doodle.cpp

// Ivan Carvalho
// Doodle - Seletiva IOI - OBI 2015
// O(n*log^2(n))
#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define S second
#define LSOne(S) (S & (-S))
using namespace std;
typedef pair<int,int> point;
typedef pair<point,point> line;
typedef pair<int,point> vertical;
const int MAXN = 3*1e5 + 10;
vector<line> jafoi;
vector<vertical> atualizacoes,sweep;
vector<int> compressao;
int ultimox,ultimoy,n,k,inter,ptr,bit[MAXN];
void update(int idx,int val){
	while(idx < MAXN){
		bit[idx] += val;
		idx += LSOne(idx);
	}
}
int read(int idx){
	int ans = 0;
	while(idx > 0){
		ans += bit[idx];
		idx -= LSOne(idx);
	}
	return ans;
}
int conta(int vaiate){
	if(vaiate == 1) return 0;
	memset(bit,0,sizeof(bit));
	inter  = 0;
	ptr = 0;
	sweep.clear();
	atualizacoes.clear();
	compressao.clear();
	for(int i =1;i<vaiate;i+=2){
		int posx = jafoi[i].F.F;
		int posy1 = jafoi[i].F.S;
		int posy2 = jafoi[i].S.S;
		if(posy1 + 1 <= posy2 - 1) atualizacoes.push_back(MP(posx,MP(posy1 + 1,posy2 - 1)));
		compressao.push_back(posy1+1);
		compressao.push_back(posy2 -1);
	}
	for(int i = 0;i<vaiate;i+=2){
		int posx1 = jafoi[i].F.F;
		int posx2 = jafoi[i].S.F;
		int posy = jafoi[i].F.S;
		posx1++;
		posx2--;
		if(!(posx1 <= posx2)) continue;
		sweep.push_back(MP(posx1 - 1,MP(-1,posy)));
		sweep.push_back(MP(posx2,MP(1,posy)));
		compressao.push_back(posy);
	}
	sort(compressao.begin(),compressao.end());
	compressao.erase(unique(compressao.begin(),compressao.end()),compressao.end());
	sort(atualizacoes.begin(),atualizacoes.end());
	sort(sweep.begin(),sweep.end());
	for(int i=0;i<sweep.size();i++){
		int x = sweep[i].first;
		int tipo = sweep[i].second.first;
		int y = sweep[i].second.second;
		y = lower_bound(compressao.begin(),compressao.end(),y) - compressao.begin() + 1;
		while(ptr < atualizacoes.size() && atualizacoes[ptr].first <= x){
			int y1 = atualizacoes[ptr].second.first;
			int y2 = atualizacoes[ptr].second.second;
			y1 = lower_bound(compressao.begin(),compressao.end(),y1) - compressao.begin() + 1;
			y2 = lower_bound(compressao.begin(),compressao.end(),y2) - compressao.begin() + 1;
			update(y1,1);
			update(y2 + 1,-1);
			ptr++;
		}
		inter += read(y)*tipo;
	}
	return inter;
}
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		int delta;
		scanf("%d",&delta);
		int x = ultimox;
		int y = ultimoy;
		if(i % 2 == 1) x += delta;
		else y += delta;
		jafoi.push_back(MP(MP(min(ultimox,x),min(ultimoy,y)),MP(max(x,ultimox),max(y,ultimoy))));
		ultimox = x;
		ultimoy = y;
	}
	int ini = 1,fim = n, meio,resp = -1,qtd=-1;
	while(ini <= fim){
		meio = (ini+fim)/2;
		int temp = conta(meio);
		if(temp >= k){
			qtd = temp;
			resp = meio;
			fim = meio - 1;
		}
		else ini = meio + 1;
	}
	if(resp == -1){
		resp = n;
		qtd = conta(n);
	}
	printf("%d %d\n",resp,qtd);
	return 0;
}