| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 103025 |
2019-03-28T19:11:32 Z |
brcode |
UFO (IZhO14_ufo) |
C++14 |
|
780 ms |
263168 KB |
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
int n,m,r,k,p;
vector<vector<int>> a;
vector<int> temp;
int remain;
struct segtree{
vector<int> v1;
int n;
segtree(int n):n(n), v1(n * 4 + 10) {}
segtree() {}
void reset(int n) {
this -> n = n;
v1.resize(n * 4 + 10);
}
void update(int curr,int l,int r,int u,int val){
// cout<<l<<" "<<r<<endl;
if(l == r){
v1[curr] = val;
return;
}
int mid = (l+r)/2;
if(u<=mid){
update(2*curr,l,mid,u,val);
}else{
update(2*curr+1,mid+1,r,u,val);
}
v1[curr] = max(v1[2*curr],v1[2*curr+1]);
}
void findfirst(int curr,int l,int r,int x){
if(remain == 0||v1[curr]<x){
//cout<<l<<" "<<r<<" "<<v1[curr]<<endl;
return;
}
if(l == r){
remain--;
temp.push_back(l);
}else{
int mid = (l+r)/2;
findfirst(2*curr,l,mid,x);
findfirst(2*curr+1,mid+1,r,x);
}
}
void findlast(int curr,int l,int r,int x){
if(remain == 0||v1[curr]<x){
return;
}
if(l == r){
remain--;
temp.push_back(l);
}else{
int mid = (l+r)/2;
findlast(2*curr+1,mid+1,r,x);
findlast(2*curr,l,mid,x);
}
}
};
segtree row[MAXN],col[MAXN];
int main(){
cin>>m>>n>>r>>k>>p;
a.resize(m+1);
for(int i=1;i<=n;i++){
col[i].reset(m);
}
a[0].resize(n+1);
for(int i=1;i<=m;i++){
row[i].reset(n);
a[i].resize(n+1);
for(int j=1;j<=n;j++){
cin>>a[i][j];
row[i].update(1,1,n,j,a[i][j]);
col[j].update(1,1,n,i,a[i][j]);
}
}
for(int i=0;i<k;i++){
temp.clear();
remain = r;
char z;
cin>>z;
int id,h;
cin>>id>>h;
if(z == 'W'){
row[id].findfirst(1,1,n,h);
for(int x:temp){
//cout<<x<<endl;
a[id][x]--;
row[id].update(1,1,n,x,a[id][x]);
col[x].update(1,1,n,id,a[id][x]);
}
}else if(z == 'E'){
row[id].findlast(1,1,n,h);
for(int x:temp){
a[id][x]--;
row[id].update(1,1,n,x,a[id][x]);
col[x].update(1,1,n,id,a[id][x]);
}
}else if(z == 'N'){
col[id].findfirst(1,1,n,h);
for(int x:temp){
a[x][id]--;
row[x].update(1,1,n,id,a[x][id]);
col[id].update(1,1,n,x,a[x][id]);
}
}else{
col[id].findlast(1,1,n,h);
for(int x:temp){
a[x][id]--;
//cout<<x<<endl;
row[x].update(1,1,n,id,a[x][id]);
col[id].update(1,1,n,x,a[x][id]);
}
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int ans = 0;
for(int i=1;i<=m-p+1;i++){
for(int j=1;j<=n-p+1;j++){
int temp = a[i+p-1][j+p-1] - a[i+p-1][j-1] - a[i-1][j+p-1] + a[i-1][j-1];
ans = max(ans,temp);
}
}
cout<<ans<<endl;
}
Compilation message
ufo.cpp: In constructor 'segtree::segtree(int)':
ufo.cpp:12:9: warning: 'segtree::n' will be initialized after [-Wreorder]
int n;
^
ufo.cpp:11:17: warning: 'std::vector<int> segtree::v1' [-Wreorder]
vector<int> v1;
^~
ufo.cpp:13:5: warning: when initialized here [-Wreorder]
segtree(int n):n(n), v1(n * 4 + 10) {}
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
63096 KB |
Output is correct |
| 2 |
Correct |
59 ms |
62968 KB |
Output is correct |
| 3 |
Correct |
65 ms |
63096 KB |
Output is correct |
| 4 |
Correct |
75 ms |
63352 KB |
Output is correct |
| 5 |
Incorrect |
175 ms |
65144 KB |
Output isn't correct |
| 6 |
Correct |
413 ms |
80468 KB |
Output is correct |
| 7 |
Runtime error |
227 ms |
171560 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
226 ms |
171500 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
189 ms |
164344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
222 ms |
171512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
251 ms |
172860 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
232 ms |
171532 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
606 ms |
107896 KB |
Output is correct |
| 14 |
Runtime error |
224 ms |
173012 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
227 ms |
171384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
224 ms |
172916 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Incorrect |
779 ms |
107740 KB |
Output isn't correct |
| 18 |
Correct |
462 ms |
103496 KB |
Output is correct |
| 19 |
Runtime error |
252 ms |
185436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
780 ms |
263168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
