Submission #788155

#	Time	Username	Problem	Language	Result	Execution time	Memory
788155		APROHACK	Seats (IOI18_seats)	C++17	11 / 100	1316 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;
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();
		}
	}
	ll 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); 
  
}

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]);
	ll alto, ancho, ans = 0;
	int minimoH = r[0], minimoC = c[0], maximoH = r[0], maximoC = c[0];
	for(int i = 0 ; i < hw ; i ++){
		//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;
		/*
		if(ancho * alto == i + 1){
			ans ++ ;
			i += min(ancho, alto) -1;
			//cout << i << endl;
		}else{
			i = ancho*alto-2;
		}
		* */
		if(ancho * alto == i+1)ans ++;
		if(i + 1 < hw){
			minimoH = min(minimoH, r[i+1]);
			minimoC = min(minimoC, c[i+1]);
			maximoH = max(maximoH, r[i+1]);
			maximoC = max(maximoC, c[i+1]);
		}
	}
	//cout << endl;
	
	
	return ans;
}

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