Submission #103031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103031	2019-03-28T19:23:18 Z	brcode	UFO (IZhO14_ufo)	C++14	35 / 100	682 ms	263168 KB

ufo

#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;
    
    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;
}

Subtask #1

35.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	57 ms	62976 KB	Output is correct
2	Correct	60 ms	62968 KB	Output is correct
3	Correct	57 ms	62968 KB	Output is correct
4	Correct	82 ms	63352 KB	Output is correct
5	Incorrect	199 ms	65784 KB	Output isn't correct
6	Correct	426 ms	81144 KB	Output is correct
7	Runtime error	254 ms	172060 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	229 ms	171612 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	207 ms	164464 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	216 ms	171644 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	230 ms	173304 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	216 ms	171640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	468 ms	108508 KB	Output is correct
14	Runtime error	255 ms	173124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	285 ms	171772 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	223 ms	173196 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Incorrect	680 ms	108572 KB	Output isn't correct
18	Correct	470 ms	104480 KB	Output is correct
19	Runtime error	252 ms	185864 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	682 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)