Submission #169067

#	Time	Username	Problem	Language	Result	Execution time	Memory
169067		abil	UFO (IZhO14_ufo)	C++14	100 / 100	1137 ms	200712 KiB

ufo

#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
//#define int long long

using namespace std;

const int N = (1e6 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

int remain;
vector<int > vec;
struct str{
	vector<int > t;
	void reset(int n){
		t.resize(n * 6 + 12);
	}
	void update(int v,int tl,int tr,int pos, int val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int mid = (tl + tr) >> 1;
		if(pos <= mid){
			update(v + v, tl, mid, pos, val);
		}
		else{
			update(v + v + 1, mid + 1, tr, pos, val);
		}
		t[v] = max(t[v + v], t[v + v + 1]);
	}
	void findfirst(int v,int tl,int tr,int x){
		if(remain == 0 || t[v] < x){
			return;
		}
		if(tl == tr){
			remain--;
			vec.pb(tl);
			return;
		}
		int mid = (tl + tr) >> 1;
		findfirst(v + v, tl, mid, x);
		findfirst(v + v + 1, mid + 1, tr, x);
	}
	void findlast(int v,int tl,int tr,int x){
		if(remain == 0 || t[v] < x){
			return;
		}
		if(tl == tr){
			remain--;
			vec.pb(tl);
			return;
		}
		int mid = (tl + tr) >> 1;
		findlast(v + v + 1, mid + 1, tr, x);
		findlast(v + v, tl, mid, x);
	}
};

str row[N], col[N];
main()
{
	int n, m, r, k, p;
	scanf("%d%d%d%d%d", &n, &m, &r, &k, &p);
	int a[n + 3][m + 3];
	memset(a, 0, sizeof(a));
	for(int i = 1;i <= m; i++){
		col[i].reset(n + 1);
	}
	for(int i = 1;i <= n; i++){
		row[i].reset(m + 1);
		for(int j = 1;j <= m; j++){
			scanf("%d", &a[i][j]);
			row[i].update(1, 1, m, j, a[i][j]);
			col[j].update(1, 1, n, i, a[i][j]);
		}
	}
	char ch;
	int id, h;
	while(k--){
		vec.clear();
		remain = r;
		cin >> ch;
		scanf("%d%d", &id, &h);
		if(ch == 'W'){
			row[id].findfirst(1, 1, m, h);
			for(auto to : vec){
				a[id][to]--;
				row[id].update(1, 1, m, to, a[id][to]);
				col[to].update(1, 1, n, id, a[id][to]);
			}
		}
		if(ch == 'N'){
			col[id].findfirst(1, 1, n, h);
			for(auto to : vec){
				a[to][id]--;
				row[to].update(1, 1, m, id, a[to][id]);
				col[id].update(1, 1, n, to, a[to][id]);
			}
		}
		if(ch == 'E'){
			row[id].findlast(1, 1, m, h);
			for(auto to : vec){
				a[id][to]--;
				row[id].update(1, 1, m, to, a[id][to]);
				col[to].update(1, 1, n, id, a[id][to]);
			}
		}
		if(ch == 'S'){
			col[id].findlast(1, 1, n, h);
			for(auto to : vec){
				a[to][id]--;
				row[to].update(1, 1, m, id, a[to][id]);
				col[id].update(1, 1, n, to, a[to][id]);
			}
		}
	}
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			int x = 0, y = 0;
			if(j >= 2){
				y = a[i][j - 1];
			}
			if(i >= 2){
				x = a[i - 1][j];
			}
			a[i][j] = a[i][j] + x + y - a[i - 1][j - 1];
		}
	}
	int ans = 0;
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m; j++){
			if(i >= p && j >= p){
				int val = a[i][j] - a[i][j - p] - a[i - p][j] + a[i - p][j - p];
				ans = max(ans, val);
			} 
		}
	}
	cout << ans;
}

Compilation message (stderr)

ufo.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
ufo.cpp: In function 'int main()':
ufo.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &r, &k, &p);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &id, &h);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100