oj.uz

답안 #425408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425408 2021-06-13T02:13:22 Z APROHACK 삶의 질 (IOI10_quality) C++17
0 / 100
 15 ms 544 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
//long long rtamx = __INT_MAX__;
struct SegTree{
	long long dd, htt, val1, mid;
	SegTree *L, *R;
	SegTree(long long l, long long  r){
		dd=l, htt=r;
		val1=0;
		mid=(dd+htt)/2;
		if(l!=r){
			L=new SegTree(l, mid);
			R=new SegTree(mid+1, r);
		}
	}
	int query(long long val){
		if(dd==htt){
			cout<<" "<< dd<<endl;
			return dd;
		}
		if(val<=L->val1){
			return L->query(val);
		}else{
			return R->query(val-L->val1);
		}
	}
	void insert(int pos, int val){
		if(dd==htt){
			cout<<dd<<endl;
			val1+=val;
			return ;
		}
		if(pos<=mid){
			L->insert(pos, val);
		}else{
			R->insert(pos, val);
		}
		val1=L->val1+R->val1;
	}

};
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int rtamx;
	SegTree *tree = new SegTree(0, R*C+1);
	bool up = true, creado = true;
	for(int x = 0 ; x < H ; x++){
		for(int y = 0 ; y < W ; y++){
			tree->insert(Q[x][y], 1);
		}
	}
	int xd = ((H*W)/2)+1;
	rtamx=tree->query(xd);
	for(int i = 0 ; i <= R-H ; i++){
		//cout<<"i"<<" "<<i<<endl;
		if(up){
			for(int j = 1 ; j <= C-W ; j++){
				//cout<<"j"<<" "<<j<<endl;
				for(int x = i ; x < i+H ; x++){
					tree->insert(Q[x][j-1], -1);
					tree->insert(Q[x][(j+W)-1], 1);
				}
				rtamx=min(rtamx, tree->query(xd));
			}
			creado=true;
			//C-W
			if((i+1<=R-H)){
				for(int x = C-W ; x < C ; x++){
					tree->insert(Q[i][x], -1);
					tree->insert(Q[(i+H)][x], 1);
				}
				rtamx=min(rtamx, tree->query(xd));
			}
		}else{
			for(int j = ((C-W)-1) ; j >=0 ; j--){
				//cout<<"j"<<" "<<j<<endl;
				for(int x = i ; x < i+H ; x++){
					tree->insert(Q[x][j], 1);
					tree->insert(Q[x][(j+W)], -1);
				}
			}
			rtamx=min(rtamx, tree->query(xd));
			if((i+1<=R-H)){
				for(int x = 0 ; x < W ; x++){
					tree->insert(Q[i][x], -1);
					tree->insert(Q[(i+H)][x], 1);
				}
				rtamx=min(rtamx, tree->query(xd));
			}
		}

		up=!up;

	}
	//cout<<rtamx<<endl;
	return rtamx;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:46:18: warning: variable 'creado' set but not used [-Wunused-but-set-variable]
   46 |  bool up = true, creado = true;
      |                  ^~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -