Submission #341132

#	Time	Username	Problem	Language	Result	Execution time	Memory
341132		tengiz05	UFO (IZhO14_ufo)	C++17	100 / 100	1126 ms	97188 KiB

ufo

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k, r, P;
vector<int> decreased;
struct segtree{
	int sz;
	vector<int> t;
	void build(int n, vector<int> v){
		assert((int)v.size() == n+1);
		sz=1;
		while(sz < n)sz<<=1;
		t.assign(sz*2, 0);
		for(int i=0;i<n;i++){
			t[i+sz] = v[i+1];
		}for(int i=sz-1;i>0;i--){
			t[i] = max(t[i<<1], t[i<<1|1]);
		}
	}
	void decrease_it(int pos){
		pos += sz;
		for(t[pos]--; pos > 1; pos >>= 1)t[pos>>1] = max(t[pos], t[pos^1]);
	}
	int remaining;
	int height;
	void going(int L, int R, int x){
		if(remaining == 0 || t[x] < height)return;
		if(R-L == 1){
			t[x]--;
			remaining--;
			decreased.pb(x-sz+1);
			return;
		}int mid = (L+R)/2;
		going(L, mid, x<<1);
		going(mid, R, x<<1|1);
		t[x] = max(t[x<<1], t[x<<1|1]);
	}
	void going_in_reverse(int L, int R, int x){
		if(remaining == 0 || t[x] < height)return;
		if(R-L == 1){
			t[x]--;
			remaining--;
			decreased.pb(x-sz+1);
			return;
		}int mid = (L+R)/2;
		going_in_reverse(mid, R, x<<1|1);
		going_in_reverse(L, mid, x<<1);
		t[x] = max(t[x<<1], t[x<<1|1]);
	}
	void decrease_them(int h){
		decreased.clear();
		remaining = r;
		height = h;
		going(0, sz, 1);
	}
	void decrease_them_in_reverse(int h){
		decreased.clear();
		remaining = r;
		height = h;
		going_in_reverse(0, sz, 1);
	}
	int get(int pos){
		return t[pos+sz];
	}
};
void solve(int test_case){
	int i, j;
	cin >> n >> m >> r >> k >> P;
	vector<vector<int>> a(n+1, vector<int> (m+1));
	vector<vector<int>> pr(n+1, vector<int> (m+1));
	vector<segtree> row(n+1);
	vector<segtree> col(m+1);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	for(i=1;i<=n;i++){
		row[i].build(m, a[i]);
	}
	for(j=1;j<=m;j++){
		vector<int> tmp;
		tmp.pb(0);
		for(i=1;i<=n;i++)tmp.pb(a[i][j]);
		col[j].build(n, tmp);
	}
	while(k--){
		char typ;
		cin >> typ;
		int pos, height;
		cin >> pos >> height;
		if(typ == 'N'){
			int x=1, y=pos;
			col[y].decrease_them(height);
			for(auto pos : decreased){
				row[pos].decrease_it(y-1);
			}
		}else if(typ == 'S'){
			int x=n, y=pos;
			col[y].decrease_them_in_reverse(height);
			for(auto pos : decreased){
				row[pos].decrease_it(y-1);
			}
		}else if(typ == 'E'){
			int x=pos, y=m;
			row[x].decrease_them_in_reverse(height);
			for(auto pos : decreased){
				col[pos].decrease_it(x-1);
			}
		}else {
			int x=pos, y=1;
			row[x].decrease_them(height);
			for(auto pos : decreased){
				col[pos].decrease_it(x-1);
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			a[i][j] = row[i].get(j-1);
		}
	}
		
/*	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cout << a[i][j] << ' ';
		}cout << '\n';
	}*/
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			pr[i][j] = pr[i][j-1] + a[i][j];
		}
		for(j=1;j<=m;j++){
			pr[i][j] += pr[i-1][j];
		}
	}
	int ans = 0;
	for(i=P;i<=n;i++){
		for(j=P;j<=m;j++){
			int area = pr[i][j] + pr[i-P][j-P];
			area -= pr[i-P][j];
			area -= pr[i][j-P];
			chmax(ans, area);
		}
	}cout << ans << '\n';
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message (stderr)

ufo.cpp: In function 'void solve(int)':
ufo.cpp:105:8: warning: unused variable 'x' [-Wunused-variable]
  105 |    int x=1, y=pos;
      |        ^
ufo.cpp:111:8: warning: unused variable 'x' [-Wunused-variable]
  111 |    int x=n, y=pos;
      |        ^
ufo.cpp:117:15: warning: unused variable 'y' [-Wunused-variable]
  117 |    int x=pos, y=m;
      |               ^
ufo.cpp:123:15: warning: unused variable 'y' [-Wunused-variable]
  123 |    int x=pos, y=1;
      |               ^

• Subtask 1: 100 / 100