Submission #103177

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103177	2019-03-29T07:38:13 Z	aesfasfasf	UFO (IZhO14_ufo)	C++14	35 / 100	861 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+1);
    }
    a[0].resize(n+1);
    for(int i=1;i<=m;i++){
        
        row[i].reset(n+1);
        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	60 ms	62972 KB	Output is correct
2	Correct	69 ms	62968 KB	Output is correct
3	Correct	64 ms	63096 KB	Output is correct
4	Correct	92 ms	63480 KB	Output is correct
5	Incorrect	314 ms	65756 KB	Output isn't correct
6	Correct	448 ms	83660 KB	Output is correct
7	Runtime error	239 ms	175224 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	246 ms	174968 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	232 ms	166064 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	273 ms	174712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	277 ms	177072 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	246 ms	174712 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	615 ms	113592 KB	Output is correct
14	Runtime error	254 ms	177160 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	275 ms	174956 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	241 ms	177144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Incorrect	772 ms	114932 KB	Output isn't correct
18	Correct	565 ms	110748 KB	Output is correct
19	Runtime error	291 ms	192248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	861 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)