Submission #788166

#	Time	Username	Problem	Language	Result	Execution time	Memory
788166		APROHACK	Seats (IOI18_seats)	C++17	0 / 100	317 ms	262144 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[1000000];
int ans;
void updetiar(int dd, int ht);
struct segTree{
	int dd, ht, mid;
	ll 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;

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);
	memset(acum, false, sizeof acum);
	ans = 0;
	updetiar(0, hw-1);
}
void updetiar(int dd, int ht){
	ll alto, ancho;
	int minimoH = minH->query(0, dd), minimoC = minC->query(0, dd), maximoH = maxH->query(0, dd), maximoC = maxC->query(0, dd), nextI;
	for(int i = dd ; i <= ht ;){
		//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 < i+20 and nextI <= ht){
			for(int j = i+1 ; j <= nextI ; j ++){
				minimoH = min(minimoH, r[j]);
				minimoC = min(minimoC, c[j]);
				maximoH = max(maximoH, r[j]);
				maximoC = max(maximoC, c[j]);
			}
		}else if(nextI <= hw){
			minimoH = min(minH->query(i+1, nextI), minimoH);
			maximoH = max(maxH->query(i+1, nextI), maximoH);
			minimoC = min(minC->query(i+1, nextI), minimoC);
			maximoC = max(maxC->query(i+1, 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) {
	
	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(min(a, b), max(a, b));
	//cout << endl;
	
	
	return ans;
}

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