Submission #788173

#	Time	Username	Problem	Language	Result	Execution time	Memory
788173		APROHACK	Seats (IOI18_seats)	C++17	17 / 100	4059 ms	64820 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;


std::vector<int> r, c;
vector<int>aux;
ll h, w, hw;

bool acum[1000002];
int ans;
void updetiar(int dd, int ht);
struct segTree{
	int dd, ht, mid;
	int val;
	bool isMax;
	segTree *L, *R;
	segTree(int l, int rr, bool maximos){
		dd = l;
		ht = rr;
		mid = (dd + ht)/2;
		val = 0;
		isMax = maximos;
		if(l != rr){
			L = new segTree(l, mid, maximos);
			R = new segTree(mid+1, ht, maximos);
			if(isMax and L->val > R->val)val = L->val;
			else if(isMax)val = R->val;
			else if(L->val < R->val)val = L->val;
			else val = R->val;
		}else{
			val = aux[l];
		}
	}
	void update(){
		if(isMax and L->val > R->val)val = L->val;
		else if(isMax)val = R->val;
		else if(L->val < R->val)val = L->val;
		else val = R->val;
	}
	void cambiar(int pos, int cuanto){
		if(dd == ht)val = cuanto;
		else{
			if(pos <= mid)L->cambiar(pos, cuanto);
			else R->cambiar(pos, cuanto);
			update();
		}
	}
	int query(int l, int rr){
		if(dd == l and rr == ht)return val;
		if( rr<= mid)return L->query(l, rr);
		if(mid < l)return R->query(l, rr);
		if(isMax){
			return max(L->query(l, mid), R->query(mid+1, rr));
		}else return min(L->query(l, mid), R->query(mid+1, rr));
	}
};

//segTree *maxH, *minH, *maxC, *minC;
vector<int>maxH, minH, maxC, minC;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r = R;
	c = C;
	h = H;
	w = W;
	hw = h*w;
	for(int i = 0 ; i < hw ; i ++)aux.pb(R[i]);
	//maxH = new segTree(0, hw-1, true);
	//minH = new segTree(0, hw-1, false);
	for(int i = 0 ; i < hw ; i ++)aux[i] = C[i];
	//maxC = new segTree(0, hw-1, true);
	//minC = new segTree(0, hw-1, false);
	for(int i = 0 ; i <= hw ; i ++)acum[i] = false;
	int mxH, mxC, mnH, mnC;
	
	for(int i = 0 ; i < hw ; i ++){
		mxH = max(R[i], mxH);
		mxC = max(C[i], mxC);
		mnH = min(R[i], mnH);
		mnC = min(C[i], mnC);
		maxH.pb(mxH);
		maxC.pb(mxC);
		minH.pb(mnH);
		minC.pb(mnC);
	}
	ans = 0;
	updetiar(0, hw-1);
}
void updetiar(int dd, int ht){
	ll alto, ancho;
	//cout << " c " << dd << " " << ht << endl;
	//int minimoH = minH->query(0, dd), minimoC = minC->query(0, dd), maximoH = maxH->query(0, dd), maximoC = maxC->query(0, dd), nextI;
	int minimoH ,minimoC , maximoH, maximoC, nextI;
	if(dd != 0){
		minimoH = minH[dd-1], minimoC = minC[dd-1], maximoH = maxH[dd-1], maximoC = maxC[dd-1];
		nextI = dd;
		minimoH = min(minimoH, r[nextI]);
		minimoC = min(minimoC, c[nextI]);
		maximoH = max(maximoH, r[nextI]);
		maximoC = max(maximoC, c[nextI]);
		minH[nextI] = minimoH;
		maxH[nextI] = maximoH;
		minC[nextI] = minimoC;
		maxC[nextI] = maximoC;
	}else{
		minimoH =  r[0];
		minimoC = c[0];
		maximoH = r[0];
		maximoC = c[0];
		minH[0] = minimoH;
		maxH[0] = maximoH;
		minC[0] = minimoC;
		maxC[0] = maximoC;
	}
	for(int i = dd ; i <= ht ;){
		//cout << i << endl;
		//alto = maxH->query(0, i) - minH->query(0, i) + 1;
		//ancho = maxC->query(0, i) - minC->query(0, i) + 1;
		alto = maximoH - minimoH + 1;
		ancho = maximoC - minimoC + 1;
		nextI = i+1;
		bool flag = false;
		if(ancho * alto == i + 1){
			//ans ++ ;
			flag = true;
			//nextI = i + min(ancho, alto);
			//cout << i << endl;
		}else{
			//nextI = ancho*alto-1;
		}
		if(nextI <= ht){
			minimoH = min(minimoH, r[nextI]);
			minimoC = min(minimoC, c[nextI]);
			maximoH = max(maximoH, r[nextI]);
			maximoC = max(maximoC, c[nextI]);
			minH[nextI] = minimoH;
			maxH[nextI] = maximoH;
			minC[nextI] = minimoC;
			maxC[nextI] = maximoC;
		}
		if(acum[i] and !flag){
			ans -- ;
			//cout << "se perdio " << i << endl;
		}else if(!acum[i] and flag){
			ans ++ ;
		}
		acum[i] = flag;
		i = nextI;
	}
}



int swap_seats(int a, int b) {
	if(a > b)swap(a, b);
	/*
	maxH->cambiar(a, r[b]);
	minH->cambiar(a, r[b]);
	maxH->cambiar(b, r[a]);
	minH->cambiar(b, r[a]);
	
	maxC->cambiar(a, c[b]);
	minC->cambiar(a, c[b]);
	maxC->cambiar(b, c[a]);	
	minC->cambiar(b, c[a]);
	* */
	
	
	
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	updetiar(a, b);
	//cout << endl;
	
	
	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30