답안 #103025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103025	2019-03-28T19:11:32 Z	brcode	UFO (IZhO14_ufo)	C++14	35 / 100	780 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;
    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) {}
     ^~~~~~~

Subtask #1

35.0 / 100.0

#	결과	실행 시간	메모리	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)