oj.uz

답안 #425322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425322 2021-06-12T21:24:46 Z dreezy 삶의 질 (IOI10_quality) C++17
60 / 100
 5000 ms 149164 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;


const int maxn = 9e6 + 5;
struct SegTree{
	int st[maxn * 4];
	int sz = 9e6;
	
	void clear(){
		memset(st, 0, sizeof(st));
	}
	
	void upd(int n, int l, int r, int ind, bool val ){
		if(l == r){
			st[n] = val;
			return;
		}
		
		int mid = (l+r) /2;
		
		if( mid >= ind)
			upd(2*n+1, l, mid, ind,val);
		else
			upd(2*n+2, mid + 1, r, ind, val);
		st[n] = st[2*n+1] + st[2*n+2];
			
	}
	
	void insert(int ind){
		upd(0,1,sz, ind, 1);
	}
	
	void erase(int ind){
		upd(0,1,sz, ind, 0);
	}
	
	
	int qry(int n, int l, int r, int k){
		if(l == r)
		{
			return l;
		}
		
		int mid = (l+r) /2;
		
		if(st[2*n+1]>=k){
			return qry(2*n+1, l, mid , k);
		}
		else if(st[2*n+2] >=k - st[2*n+1]){
			return qry(2*n+2, mid + 1,r,  k - st[2*n+1]);
		}
		else
			return -1;
	}
	
	int qry(int k){
		return qry(0,1,sz, k);
	}
	
	
};

/*
int getmedian(){
	int cnt = 0;
	int median = -1;
	for(int a : active){
		if(cnt == active.size() / 2){
			median = a;
			break;
		}
		cnt++;
	}
	return median;
}
*/
SegTree active;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	
	
	active.clear();
	for(int top = 0; top < H; top ++){
		for(int left = 0; left < W; left++ ){
			active.insert(Q[top][left]);
		}
	}
	int mid = (H * W ) /2 +1;
	//cout << mid<<endl;
	
	int ans = active.qry(mid);
	//cout << active.qry(mid)<<endl;
	for(int top = 0; top <= R - H; top++){
		
		//cout << top <<":\n";
		//if top % 2 === 0, we go from left to right
		
		if(top % 2 == 0){
			
			if(top > 0){
				for(int left = 0; left < W; left++ ){
					active.erase(Q[top - 1][left]);
					active.insert(Q[top + H - 1][left]);
				}
				ans = min(ans, active.qry(mid));
			}
			for(int left = 1; left <=C - W;left++){
			//iterate left boundary of rectangle
				//cout << left << "->";
				for(int t = top; t < top + H; t++){
					active.erase(Q[t][left - 1]);
					active.insert(Q[t][left + W - 1]);
				}
				ans = min(ans, active.qry(mid));
			}
		}
		else{
			if(top > 0){
				for(int right =  C - 1; right >= C - W; right-- ){
					active.erase(Q[top - 1][right]);
					active.insert(Q[top + H - 1][right]);
				}
				ans = min(ans,active.qry(mid));
			}
			//we go from right to left
			for(int right = C  - 2; right >=W - 1; right--){
				//cout << right <<"->";
			//iterate left boundary of rectangle
				for(int t = top; t < top + H; t++){
					active.erase(Q[t][right + 1]);
					active.insert(Q[t][right - W +1]);
				}
				ans = min(ans, active.qry(mid));
			}
		}
	
	//cout << endl;
	}
	
	return ans;

}

/***********/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 141220 KB Output is correct
2 Correct 68 ms 141252 KB Output is correct
3 Correct 75 ms 141304 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 141220 KB Output is correct
2 Correct 68 ms 141252 KB Output is correct
3 Correct 75 ms 141304 KB Output is correct
4 Correct 97 ms 141592 KB Output is correct
5 Correct 111 ms 141508 KB Output is correct
6 Correct 83 ms 141532 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 141220 KB Output is correct
2 Correct 68 ms 141252 KB Output is correct
3 Correct 75 ms 141304 KB Output is correct
4 Correct 97 ms 141592 KB Output is correct
5 Correct 111 ms 141508 KB Output is correct
6 Correct 83 ms 141532 KB Output is correct
7 Correct 1137 ms 142812 KB Output is correct
8 Correct 126 ms 142788 KB Output is correct
9 Correct 1125 ms 142688 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 141220 KB Output is correct
2 Correct 68 ms 141252 KB Output is correct
3 Correct 75 ms 141304 KB Output is correct
4 Correct 97 ms 141592 KB Output is correct
5 Correct 111 ms 141508 KB Output is correct
6 Correct 83 ms 141532 KB Output is correct
7 Correct 1137 ms 142812 KB Output is correct
8 Correct 126 ms 142788 KB Output is correct
9 Correct 1125 ms 142688 KB Output is correct
10 Execution timed out 5064 ms 149164 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 141220 KB Output is correct
2 Correct 68 ms 141252 KB Output is correct
3 Correct 75 ms 141304 KB Output is correct
4 Correct 97 ms 141592 KB Output is correct
5 Correct 111 ms 141508 KB Output is correct
6 Correct 83 ms 141532 KB Output is correct
7 Correct 1137 ms 142812 KB Output is correct
8 Correct 126 ms 142788 KB Output is correct
9 Correct 1125 ms 142688 KB Output is correct
10 Execution timed out 5064 ms 149164 KB Time limit exceeded
11 Halted 0 ms 0 KB -