oj.uz

Submission #788173

# Submission time Handle Problem Language Result Execution time Memory
788173 2023-07-19T21:21:12 Z APROHACK Seats (IOI18_seats) C++17
17 / 100
 4000 ms 64820 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 57 ms 924 KB Output is correct
14 Correct 54 ms 912 KB Output is correct
15 Correct 53 ms 916 KB Output is correct
16 Correct 54 ms 852 KB Output is correct
17 Correct 53 ms 852 KB Output is correct
18 Correct 53 ms 916 KB Output is correct
19 Correct 58 ms 928 KB Output is correct
20 Correct 54 ms 916 KB Output is correct
21 Correct 54 ms 972 KB Output is correct
22 Correct 54 ms 936 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 49992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 852 KB Output is correct
2 Correct 92 ms 5216 KB Output is correct
3 Correct 261 ms 64540 KB Output is correct
4 Correct 272 ms 64744 KB Output is correct
5 Correct 261 ms 64808 KB Output is correct
6 Correct 280 ms 64820 KB Output is correct
7 Correct 262 ms 64700 KB Output is correct
8 Correct 261 ms 64812 KB Output is correct
9 Correct 293 ms 64712 KB Output is correct
10 Correct 271 ms 64688 KB Output is correct
11 Correct 278 ms 64800 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1360 KB Output is correct
2 Correct 13 ms 1360 KB Output is correct
3 Correct 17 ms 1360 KB Output is correct
4 Correct 63 ms 1348 KB Output is correct
5 Correct 517 ms 1688 KB Output is correct
6 Execution timed out 4059 ms 50388 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 57 ms 924 KB Output is correct
14 Correct 54 ms 912 KB Output is correct
15 Correct 53 ms 916 KB Output is correct
16 Correct 54 ms 852 KB Output is correct
17 Correct 53 ms 852 KB Output is correct
18 Correct 53 ms 916 KB Output is correct
19 Correct 58 ms 928 KB Output is correct
20 Correct 54 ms 916 KB Output is correct
21 Correct 54 ms 972 KB Output is correct
22 Correct 54 ms 936 KB Output is correct
23 Execution timed out 4016 ms 49992 KB Time limit exceeded
24 Halted 0 ms 0 KB -