oj.uz

Submission #138764

# Submission time Handle Problem Language Result Execution time Memory
138764 2019-07-30T10:01:57 Z MAMBA Seats (IOI18_seats) C++17
11 / 100
 4000 ms 55656 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)
typedef vector<int> vi;

int MIN(int a, int b) {
	return a < b ? a : b;
}
int MAX(int a, int b) {
	return b < a ? a : b;
}

const int N = 1e6 + 10;
int n;

template<int(*f)(int , int)>
struct seg {
	int arr[N << 1];
	seg() {
		memset(arr, f(0 , 63) ^ 63 , sizeof(arr));
	}
	inline void Upd(int p , int val) {
		for (arr[p += n] = val; p > 1; p >>= 1)
			arr[p >> 1] = f(arr[p] , arr[p ^ 1]);
	}
	inline int Get(int l , int r) {
		int res = f(0 , (int)1e9) ^ (int)1e9;
		for (l += n , r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res = f(res , arr[l++]);
			if (r & 1) res = f(res , arr[--r]);
		}
		return res;
	}
};


seg<MIN> mR , mC;
seg<MAX> xR , xC;

vi R , C;
/*
int solve(int me) {
//	cout << " ::::" << me << endl;

	if (me == n + 1) return 0;
	int sz = (xR.Get(0 , me) - mR.Get(0 , me) + 1) *
		(xC.Get(0 , me) - mC.Get(0 , me) + 1); 
//	cout << " : " << sz << endl;


	if (sz == me) return solve(me + 1) + 1;
	return solve(sz);
}
*/

int solve(int ptr = 0, int l1 = R[0] , int l2 = R[0] , int r1 = C[0] , int r2 = C[0]) {

	if (ptr == n) return 0;

	int sz = (l2 - l1 + 1) * (r2 - r1 + 1);

//	cout << ptr << ' '<< l1 << ' '<< l2 << ' ' << r1 << ' ' << r2 << endl;
	
//	int junk;
//	cin >> junk;


	int l_ = R[ptr];
	int r_ = C[ptr];
	if (l_ >= l1 && l_ <= l2 && r_ >= r1 && r_ <= r2) {
		ptr++;
		//cout << ptr - 1 << " :: " << endl;
		if (ptr == sz) return 1 + solve(ptr, l1 , l2 , r1 , r2);
		return solve(ptr , l1 , l2 , r1 ,r2);
	}
	if (r_ > r2) r2 = r_;
	if (r_ < r1) r1 = r_;
	if (l_ > l2) l2 = l_;
	if (l_ < l1) l1 = l_;

	return solve(ptr, l1 , l2 , r1 , r2);
	
}

void give_initial_chart(int H, int W, vi R_, vi C_) {
	R = R_, C = C_;
	n = H * W;
	/*
	rep(i , 0 , n) {
		mR.Upd(i , R[i]);
		mC.Upd(i , C[i]);
		xR.Upd(i , R[i]);
		xC.Upd(i , C[i]);
	}
	*/
	//cout << solve(1) << endl;
	
	//cout << "GOOD" << endl;
	return;
}


int swap_seats(int a, int b) {
	swap(R[a] , R[b]);
	swap(C[a] , C[b]);
/*
	mR.Upd(a , R[a]);
	mC.Upd(a , C[a]);
	xR.Upd(a , R[a]);
	xC.Upd(a , C[a]);
	mR.Upd(b , R[b]);
	mC.Upd(b , C[b]);
	xR.Upd(b , R[b]);
	xC.Upd(b , C[b]);

	//cout << "DONE" << endl;
*/

//	cout << "DONE" << endl;
	return solve();

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 32 ms 31736 KB Output is correct
3 Correct 31 ms 31736 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 32 ms 31736 KB Output is correct
6 Correct 32 ms 31704 KB Output is correct
7 Correct 31 ms 31736 KB Output is correct
8 Correct 31 ms 31800 KB Output is correct
9 Correct 32 ms 31736 KB Output is correct
10 Correct 31 ms 31736 KB Output is correct
11 Correct 31 ms 31736 KB Output is correct
12 Correct 32 ms 31736 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 32 ms 31736 KB Output is correct
3 Correct 31 ms 31736 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 32 ms 31736 KB Output is correct
6 Correct 32 ms 31704 KB Output is correct
7 Correct 31 ms 31736 KB Output is correct
8 Correct 31 ms 31800 KB Output is correct
9 Correct 32 ms 31736 KB Output is correct
10 Correct 31 ms 31736 KB Output is correct
11 Correct 31 ms 31736 KB Output is correct
12 Correct 32 ms 31736 KB Output is correct
13 Correct 155 ms 31940 KB Output is correct
14 Correct 154 ms 31940 KB Output is correct
15 Correct 155 ms 31988 KB Output is correct
16 Correct 225 ms 31992 KB Output is correct
17 Correct 155 ms 31936 KB Output is correct
18 Correct 174 ms 31864 KB Output is correct
19 Correct 179 ms 31964 KB Output is correct
20 Correct 194 ms 31992 KB Output is correct
21 Correct 218 ms 32104 KB Output is correct
22 Correct 192 ms 32076 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 31984 KB Output is correct
2 Correct 1170 ms 33728 KB Output is correct
3 Execution timed out 4075 ms 55200 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 32628 KB Output is correct
2 Correct 59 ms 32728 KB Output is correct
3 Correct 69 ms 32728 KB Output is correct
4 Correct 218 ms 32748 KB Output is correct
5 Correct 1287 ms 33012 KB Output is correct
6 Execution timed out 4019 ms 55656 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 32 ms 31736 KB Output is correct
3 Correct 31 ms 31736 KB Output is correct
4 Correct 31 ms 31732 KB Output is correct
5 Correct 32 ms 31736 KB Output is correct
6 Correct 32 ms 31704 KB Output is correct
7 Correct 31 ms 31736 KB Output is correct
8 Correct 31 ms 31800 KB Output is correct
9 Correct 32 ms 31736 KB Output is correct
10 Correct 31 ms 31736 KB Output is correct
11 Correct 31 ms 31736 KB Output is correct
12 Correct 32 ms 31736 KB Output is correct
13 Correct 155 ms 31940 KB Output is correct
14 Correct 154 ms 31940 KB Output is correct
15 Correct 155 ms 31988 KB Output is correct
16 Correct 225 ms 31992 KB Output is correct
17 Correct 155 ms 31936 KB Output is correct
18 Correct 174 ms 31864 KB Output is correct
19 Correct 179 ms 31964 KB Output is correct
20 Correct 194 ms 31992 KB Output is correct
21 Correct 218 ms 32104 KB Output is correct
22 Correct 192 ms 32076 KB Output is correct
23 Execution timed out 4041 ms 55124 KB Time limit exceeded
24 Halted 0 ms 0 KB -