Submission #171943

#	Time	Username	Problem	Language	Result	Execution time	Memory
171943		Swan	UFO (IZhO14_ufo)	C++14	90 / 100	2060 ms	153224 KiB

ufo

#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
//#define int long long
using namespace std;

const int maxn = 100004;

int n,m,r,k,p;

/*WE-0 NS-1*/

vector<vector<int> > tree[4];
vector<vector<int> > pref;

void increment(int dir,int num,int v,int l,int r,int need,int val){
    if(l == r){
        tree[dir][num][v]+=val;
        return;
    }
    int m = (l+r)/2;
    if(need<=m)increment(dir,num,v*2,l,m,need,val);
    else increment(dir,num,v*2+1,m+1,r,need,val);
    tree[dir][num][v] = max(tree[dir][num][v*2],tree[dir][num][v*2+1]);
}

int find_on_segm_l(int dir,int num,int v,int l,int r,int need){
    if(l == r){
        return l;
    }
    int m = (l+r)/2;
    if(tree[dir][num][v*2]>=need)return find_on_segm_l(dir,num,v*2,l,m,need);
    else if(tree[dir][num][v*2+1]>=need)return find_on_segm_l(dir,num,v*2+1,m+1,r,need);
    else return -1;
}

int find_on_segm_r(int dir,int num,int v,int l,int r,int need){
    if(l == r){
        return l;
    }
    int m = (l+r)/2;
    if(tree[dir][num][v*2+1]>=need)return find_on_segm_r(dir,num,v*2+1,m+1,r,need);
    else if(tree[dir][num][v*2]>=need)return find_on_segm_r(dir,num,v*2,l,m,need);
    else return -1;
}

int get_max_l(int dir,int num,int v,int l,int r,int le,int re,int need){
    if(l >= le && r <= re){
        if(tree[dir][num][v]>=need)return find_on_segm_l(dir,num,v,l,r,need);
        else return -1;
    }
    if(l > re || r < le)return -1;
    int m = (l+r)/2;
    int a,b;
    a = get_max_l(dir,num,v*2,l,m,le,re,need);
    b = get_max_l(dir,num,v*2+1,m+1,r,le,re,need);
    if(a!= -1)return a;
    else return b;
}


int get_max_r(int dir,int num,int v,int l,int r,int le,int re,int need){
    if(l >= le && r <= re){
        if(tree[dir][num][v]>=need)return find_on_segm_r(dir,num,v,l,r,need);
        else return -1;
    }
    if(l > re || r < le)return -1;
    int m = (l+r)/2;
    int a,b;
    a = get_max_r(dir,num,v*2,l,m,le,re,need);
    b = get_max_r(dir,num,v*2+1,m+1,r,le,re,need);
    if(b!= -1)return b;
    else return a;
}

int get_cell(int v,int l,int r,int x,int y){
    if(l == r)return tree[0][x][v];
    int m = (l+r)/2;
    if(y<=m)return get_cell(v*2,l,m,x,y);
    else return get_cell(v*2+1,m+1,r,x,y);
}

void update_cell(int x,int y,int val){
    increment(0,x,1,0,m-1,y,val);
    increment(1,y,1,0,n-1,x,val);
}

void solve_w(int x,int need){
    int cnt = r;
    int l,r;l = 0;r = m-1;
    while(cnt && (l!=m)){
        int w = get_max_l(0,x,1,0,m-1,l,r,need);
        if(w == -1)break;
        cnt--;
        l = w;
        update_cell(x,l,-1);
        l++;
    }
}

void solve_e(int x,int need){
    int cnt = r;
    int l,r;l = 0;r = m-1;
    while(cnt && (r>=0)){
        int w = get_max_r(0,x,1,0,m-1,l,r,need);
        if(w == -1)break;
        cnt--;
        r = w;
        update_cell(x,r,-1);
        r--;
    }
}

void solve_n(int x,int need){
    int cnt = r;
    int l,r;l = 0;r = n-1;
    while(cnt && (l!=n)){
        int w = get_max_l(1,x,1,0,n-1,l,r,need);
        if(w == -1)break;
        cnt--;
        l = w;
        update_cell(l,x,-1);
        l++;
    }
}

void solve_s(int x,int need){
    int cnt = r;
    int l,r;l = 0;r = n-1;
    while(cnt && (r>=0)){
        int w = get_max_r(1,x,1,0,n-1,l,r,need);
        if(w == -1)break;
        cnt--;
        r = w;
        update_cell(r,x,-1);
        r--;
    }
}

void print(){
    for(int i(0); i < n;i++){
        for(int j(0); j < m;j++){
            int now = get_cell(1,0,m-1,i,j);
            int tox = i+1;int toy = j+1;
            pref[tox][toy] = now;
            pref[tox][toy]+=pref[tox-1][toy];
            pref[tox][toy]+=pref[tox][toy-1];
            pref[tox][toy]-=pref[tox-1][toy-1];
        }
    }
}

int get_sum(int x1,int y1,int x2,int y2){
    int res = 0;
    res+=pref[x2][y2];
    res-=pref[x2][y1-1];
    res-=pref[x1-1][y2];
    res+=pref[x1-1][y1-1];
    return res;
}

main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> r >> k >> p;
    pref.resize(n+2);
    for(int i(0); i <= n;i++)pref[i].resize(m+2);
    tree[0].resize(n);
    tree[1].resize(m);
    tree[2].resize(n);
    tree[3].resize(m);
    for(int i(0); i < n;i++){
        tree[0][i].resize(4*m);
        tree[2][i].resize(4*m);
    }
    for(int i(0); i < m;i++){
        tree[1][i].resize(4*n);
        tree[3][i].resize(4*n);
    }
    for(int i(0); i < n;i++){
        for(int j(0); j < m;j++){
            int val; cin >> val;
            update_cell(i,j,val);
        }
    }
    for(int i(0); i < k;i++){
        char c; cin >> c;
        int x,need; cin >> x >> need;
        x--;
        if(c == 'W')solve_w(x,need);
        if(c == 'E')solve_e(x,need);
        if(c == 'N')solve_n(x,need);
        if(c == 'S')solve_s(x,need);
    }
    print();
    int ans = 0;
    for(int i(1);i<=n;i++){
        for(int j(1);j<=m;j++){
            int x1 = i;
            int y1 = j;
            int x2 = i+p-1;
            int y2 = j+p-1;
            if(x2 <= n && y2<=m)ans = max(ans,get_sum(x1,y1,x2,y2));
        }
    }
    cout << ans;
    return 0;
}
/*

*/

Compilation message (stderr)

ufo.cpp:164:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 90 / 100