Submission #103024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103024	2019-03-28T19:09:34 Z	brcode	UFO (IZhO14_ufo)	C++14	35 / 100	757 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	63 ms	62968 KB	Output is correct
2	Correct	61 ms	62968 KB	Output is correct
3	Correct	56 ms	63096 KB	Output is correct
4	Correct	77 ms	63480 KB	Output is correct
5	Incorrect	195 ms	65724 KB	Output isn't correct
6	Correct	417 ms	83576 KB	Output is correct
7	Runtime error	249 ms	172024 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	219 ms	171768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	191 ms	164508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	225 ms	171564 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	231 ms	173156 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	221 ms	171792 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	487 ms	112040 KB	Output is correct
14	Runtime error	221 ms	173176 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	226 ms	171752 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	228 ms	173220 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Incorrect	719 ms	116488 KB	Output isn't correct
18	Correct	508 ms	108920 KB	Output is correct
19	Runtime error	355 ms	185936 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	757 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)