oj.uz

Submission #976502

# Submission time Handle Problem Language Result Execution time Memory
976502 2024-05-06T15:48:30 Z LaviniaTornaghi Quality Of Living (IOI10_quality) C++14
60 / 100
 5000 ms 28496 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 227 ms 5980 KB Output is correct
8 Correct 21 ms 6528 KB Output is correct
9 Correct 233 ms 6428 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 227 ms 5980 KB Output is correct
8 Correct 21 ms 6528 KB Output is correct
9 Correct 233 ms 6428 KB Output is correct
10 Execution timed out 5074 ms 28496 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2444 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 227 ms 5980 KB Output is correct
8 Correct 21 ms 6528 KB Output is correct
9 Correct 233 ms 6428 KB Output is correct
10 Execution timed out 5074 ms 28496 KB Time limit exceeded
11 Halted 0 ms 0 KB -