제출 #976502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976502		LaviniaTornaghi	삶의 질 (IOI10_quality)	C++14	60 / 100	5074 ms	28496 KiB

quality

#include <bits/stdc++.h>
using namespace std;
#include "grader.h"

struct SegTree{
	int tmp=1, target, MAXN;
	vector<int> tree;
	void init(int a, int b){
		target = a; MAXN=b;
		while(tmp<=MAXN) tmp*=2;
		tree.resize(2*tmp);
	}
	void update(int p, int d){
		tree[p+tmp]+=d;
		p=(p+tmp)/2; 
		while(p){
			tree[p]=tree[p*2]+tree[p*2+1];
			p/=2;
		}
	}
	int query(){ return query(1,0,tmp-1,0);}
	int query(int i, int l, int r, int sl){ 
		if(l==r) return i-tmp;
		int m = (l+r)/2;
		if(sl+tree[i*2]>target)return query(i*2,l,m,sl);
		else return query(i*2+1,m+1,r,sl+tree[i*2]);
	}

};

SegTree st;

void addcolumn(vector<vector<int>> &q,int c, int sq, int eq){
	for(int i=sq;i<eq;i++) st.update(q[i][c],1);
}
void removecolumn(vector<vector<int>> &q,int c, int sq, int eq){
	for(int i=sq;i<eq;i++) st.update(q[i][c],-1);
}
void addrow(vector<vector<int>> &q,int r, int sq, int eq){
	for(int i=sq;i<eq;i++) st.update(q[r][i],1);
}
void removerow(vector<vector<int>> &q,int r, int sq, int eq){
	for(int i=sq;i<eq;i++) st.update(q[r][i],-1);
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> q(R,vector<int>(C)); st.init((H*W)/2, R*C+10);
	for(int i=0;i<R;i++)
		for(int j=0;j<C;j++){
			q[i][j]=Q[i][j];
			if(i<H && j<W)
				st.update(q[i][j],1);
		}
	int ans = INT_MAX;
	for(int i=0;i<=R-H;i++){
		if(!(i%2)){
			for(int j=1;j<=C-W;j++){
				ans = min(ans, st.query());
				removecolumn(q,j-1,i,i+H);
				addcolumn(q,j+W-1,i,i+H);
			}
			ans = min(ans, st.query());
			removerow(q,i,C-W,C);
			if(i+H<R)addrow(q,i+H,C-W,C);
		}else{
			for(int j=C-W-1;j>=0;j--){
				ans = min(ans, st.query());
				removecolumn(q,j+W,i,i+H);
				addcolumn(q,j,i,i+H);
			}
			ans = min(ans, st.query());
			removerow(q,i,0,W);
			if(i+H<R) addrow(q,i+H,0,W);
		}
	}
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20