oj.uz

Submission #169067

# Submission time Handle Problem Language Result Execution time Memory
169067 2019-12-18T09:12:14 Z abil UFO (IZhO14_ufo) C++14
100 / 100
 1137 ms 200712 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 46 ms 47352 KB Output is correct
3 Correct 46 ms 47512 KB Output is correct
4 Correct 62 ms 47864 KB Output is correct
5 Correct 136 ms 51040 KB Output is correct
6 Correct 311 ms 75792 KB Output is correct
7 Correct 502 ms 115324 KB Output is correct
8 Correct 410 ms 111736 KB Output is correct
9 Correct 608 ms 106292 KB Output is correct
10 Correct 648 ms 110712 KB Output is correct
11 Correct 520 ms 110200 KB Output is correct
12 Correct 668 ms 110908 KB Output is correct
13 Correct 767 ms 111736 KB Output is correct
14 Correct 654 ms 110216 KB Output is correct
15 Correct 780 ms 112524 KB Output is correct
16 Correct 445 ms 112376 KB Output is correct
17 Correct 1114 ms 116360 KB Output is correct
18 Correct 423 ms 107384 KB Output is correct
19 Correct 572 ms 122872 KB Output is correct
20 Correct 1137 ms 200712 KB Output is correct