Submission #338298

#	Time	Username	Problem	Language	Result	Execution time	Memory
338298		Tosic	UFO (IZhO14_ufo)	C++14	100 / 100	1461 ms	212380 KiB

ufo

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;

int n, m, r, k, p;
vector<vector<int> > a, rv;
vector<vector<long long> > c;
//vector<int> rv;

struct segtree
{
	vector<int> tree;
	vector<int> resIdx;
	bool isC;
	int rowCol;
	int n, glR;
	segtree(){

	}
	void init(int sz, int rowCol, bool isC){
		n = sz;
		tree.resize(4*n+10, 0);
		this->isC = isC;
		this->rowCol = rowCol;
		init1(0, 0, n-1);
	}
	void kidsO(int idx){
		tree[idx] = max(tree[idx*2+1], tree[idx*2+2]);
	}
	void init1(int idx, int l, int r){
		if(idx >= tree.size()){
			return;
		}
		if(l == r){
			if(isC){
				tree[idx] = a[l][rowCol];
				//cerr << tree[idx] << '\n';
			} else {
				tree[idx] = a[rowCol][l];
			}
			return;
		}
		int mid = (l+r)/2;
		init1(idx*2+1, l ,mid);
		init1(idx*2+2, mid+1, r);
		kidsO(idx);
	}
	void getF(int idx, int l, int r, int x){
		if(idx >= tree.size()){
			return;
		}
		// first index so a[l] >= x
		if(tree[idx] < x){
			return;
		}
		if(l == r){
			--glR;////cerr << x << ' ' << tree[idx] << ' '<< l << '\n';
			resIdx.push_back(l);
			return;
		}
		int mid = (l+r)/2;
		if(tree[1+2*idx] >= x){
			getF(idx*2+1, l, mid, x);

		}if(glR){
				getF(idx*2+2, mid+1, r, x);
			}
			return;
		return;
	}
	void getL(int idx, int l, int r, int x){
		if(idx >= tree.size()){
			return;
		}

		// lst index so a[l] >= x
		if(tree[idx] < x){
			return;
		}
		if(l == r){
			////cerr << glR << '\n';
			--glR;
			resIdx.push_back(l);
			return;
		}
		int mid = (l+r)/2;
		if(tree[2+2*idx] >= x){
			getL(idx*2+2, mid+1, r, x);
		}
		if(glR){
			getL(2*idx+1, l, mid, x);
		}
	}
	void upd(int idx, int l, int r, int x, int newV){
		if(idx >= tree.size()){
			return;
		}

		if(l == r){
			tree[idx] += newV;
			return;
		}
		int mid = (l+r)/2;
		if(x<=mid){
			upd(2*idx+1, l, mid, x, newV);
		}
		if(x > mid){
			upd(2*(idx+1), mid+1, r, x, newV);
		}
		kidsO(idx);
	}
	int query(int idx, int l, int r, int qL, int qR){
		if(idx >= tree.size()){
			return 0;
		}

		if(l > qR or r < qL){
			return 0;
		}
		if(l >=qL and r <= qR){
			return tree[idx];
		}
		int mid = (l+r)/2;
		return max(query(idx*2+1, l, mid, qL, qR), query(idx*2+2, mid+1, r, qL, qR));
	}
};

vector<segtree> rTrees, cTrees;

long long tmpS(int x, int y){
	if(x < 0 or y < 0){
		return 0;
	}
	return c[x][y];
}

long long getMax(){
	for(int i = 0; i < m; ++i){
		c[0][i] = a[0][i];
		if(i){
			c[0][i] += c[0][i-1];
		}
	}
	for(int i = 0; i < n; ++i){
		c[i][0] = a[i][0];
		if(i){
			c[i][0] += c[i-1][0];
		}
	}
	for(int i = 1; i < n; ++i){
		for(int j = 1; j < m; ++j){
			c[i][j] = a[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
		}
	}
	long long res = 0;
	for(int i = 0; i < n-p+1; ++i){
		for(int j = 0; j < m-p+1; ++j){
			res = max(tmpS(i+p-1, j+p-1) - tmpS(i+p-1, j-1) - tmpS(i-1, j+p-1) + tmpS(i-1, j-1), res);
		}
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m >> r >> k >> p;
	a.resize(n, vector<int>(m));
	c.resize(n, vector<long long>(m));
	rv.resize(m, vector<int>(n));
	//rv.resize(m, 0);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			cin >> a[i][j];
		}
		rTrees.push_back(segtree());
		rTrees[i].init(m, i, 0);
	}
	for(int i = 0; i < m; ++i){
		for(int j = 0;j<n; ++ j){
			rv[i][j] = a[j][i];
		}
		cTrees.push_back(segtree());
		cTrees[i].init(n, i, 1);
		rv[i].clear();
	}
	for(int i = 0; i < k; ++i){
		char c;
		int h, y;
		cin >> c >> y >> h;
		y--;
		//for(int j = 0; j < r; ++j){
			if(c == 'N'){
				cTrees[y].resIdx.clear();
				cTrees[y].glR = r;
				cTrees[y].getF(0, 0, n-1, h);
				for(auto tmp : cTrees[y].resIdx){
					cTrees[y].upd(0, 0, n-1, tmp, -1);
					rTrees[tmp].upd(0, 0, m-1, y, -1);
					////cerr << tmp << ' ' << y << '\n';
					a[tmp][y]--;
				}
				cTrees[y].resIdx.clear();
			}
			if(c == 'S'){
				cTrees[y].resIdx.clear();
				cTrees[y].glR =r;
				cTrees[y].getL(0, 0, n-1, h);
				for(auto tmp : cTrees[y].resIdx){
					cTrees[y].upd(0, 0, n-1, tmp, -1);
					rTrees[tmp].upd(0, 0, m-1, y, -1);
					////cerr << tmp << ' ' <<  y<< '\n';
					a[tmp][y]--;
				}
				cTrees[y].resIdx.clear();
			}
			if(c == 'W'){
				rTrees[y].resIdx.clear();
				rTrees[y].glR = r;
				rTrees[y].getF(0, 0, m-1, h);
				for(auto tmp : rTrees[y].resIdx){
					rTrees[y].upd(0, 0, m-1, tmp, -1);
					cTrees[tmp].upd(0, 0, n-1, y, -1);
					////cerr << y << ' ' << tmp << '\n';
					a[y][tmp]--;
				}
				rTrees[y].resIdx.clear();

			}
			if(c == 'E'){
				rTrees[y].resIdx.clear();
				rTrees[y].glR = r;
				rTrees[y].getL(0, 0, m-1, h);
				for(auto tmp : rTrees[y].resIdx){
					rTrees[y].upd(0, 0, m-1, tmp, -1);
					cTrees[tmp].upd(0, 0, n-1, y, -1);
					////cerr << y << ' ' << tmp << '\n';
					a[y][tmp]--;
				}
				rTrees[y].resIdx.clear();
			}
		//}
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			//cerr << a[i][j] << ' ';
		}
		//cerr << '\n';
	}
	cout << getMax();
}
/*4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
E 2 1
S 4 1
S 7 1*/

Compilation message (stderr)

ufo.cpp: In member function 'void segtree::init1(int, int, int)':
ufo.cpp:31:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if(idx >= tree.size()){
      |      ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getF(int, int, int, int)':
ufo.cpp:49:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   if(idx >= tree.size()){
      |      ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::getL(int, int, int, int)':
ufo.cpp:72:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if(idx >= tree.size()){
      |      ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
ufo.cpp:95:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   if(idx >= tree.size()){
      |      ~~~~^~~~~~~~~~~~~~
ufo.cpp: In member function 'int segtree::query(int, int, int, int, int)':
ufo.cpp:113:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   if(idx >= tree.size()){
      |      ~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100