Submission #16956

#	Time	Username	Problem	Language	Result	Execution time	Memory
16956		erdemkiraz	UFO (IZhO14_ufo)	C++98	100 / 100	1259 ms	205152 KiB

ufo

#ifdef D
#include "header.h"
#else
#include "bits/stdc++.h"
#endif

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 1e6 + 5;

int n, m, r, k, p;

class tree{ public:
    int n;
    vector < int > t;
    void init(int n) {
        this -> n = n;
        t.resize(n * 4 + 5, 0);
    }
    void update(int x, int l, int r, int x1, int k) {
        if(l == r) {
            t[x] += k;
            return;
        }
        int m = l + r >> 1;
        if(x1 <= m)
            update(x + x, l, m, x1, k);
        else
            update(x + x + 1, m + 1, r, x1, k);
        t[x] = max(t[x + x], t[x + x + 1]);
    }
    int getL(int x, int l, int r, int i, int k) {
        if(r < i or t[x] < k) {
            return 0;
        }
        if(l == r)
            return l;
        int m = l + r >> 1;
        int res = getL(x + x, l, m, i, k);
        if(res)
            return res;
        return getL(x + x + 1, m + 1, r, i, k);
    }
    int getR(int x, int l, int r, int i, int k) {
        if(i < l or t[x] < k) {
            return 0;
        }
        if(l == r)
            return l;
        int m = l + r >> 1;
        int res = getR(x + x + 1, m + 1, r, i, k);
        if(res)
            return res;
        return getR(x + x, l, m, i, k);
    }
    void update(int x, int k) {
        update(1, 1, n, x, k);
    }
    int getL(int i, int k) {
        return getL(1, 1, n, i, k);
    }
    int getR(int i, int k) {
        return getR(1, 1, n, i, k);
    }
};

tree row[N], col[N];
vector < int > a[N], dp[N];

int main () {
    
    scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
    
    for(int i = 0; i <= n; i++) {
        row[i].init(m);
        a[i].resize(m + 1);
        dp[i].resize(m + 1, 0);
    }
    
    for(int i = 1; i <= m; i++) {
        col[i].init(n);
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);
            a[i][j] = x;
            row[i].update(j, x);
            col[j].update(i, x);
        }
    }
    
    for(int i = 1; i <= k; i++) {
        char c;
        int x, p;
        scanf(" %c %d %d", &c, &x, &p);
        if(c == 'W') {
            int pos = 1;
            for(int it = 0; it < r; it++) {
                int nextPos = row[x].getL(pos, p);
                if(!nextPos)
                    break;
                row[x].update(nextPos, -1);
                col[nextPos].update(x, -1);
                a[x][nextPos]--;
                pos = nextPos + 1;
            }
        }
        if(c == 'E') {
            int pos = m;
            for(int it = 0; it < r; it++) {
                int nextPos = row[x].getR(pos, p);
                if(!nextPos)
                    break;
                row[x].update(nextPos, -1);
                col[nextPos].update(x, -1);
                a[x][nextPos]--;
                pos = nextPos - 1;
            }
        }
        if(c == 'N') {
            int pos = 1;
            for(int it = 0; it < r; it++) {
                int nextPos = col[x].getL(pos, p);
                if(!nextPos)
                    break;
                row[nextPos].update(x, -1);
                col[x].update(nextPos, -1);
                a[nextPos][x]--;
                pos = nextPos + 1;
            }
        }
        if(c == 'S') {
            int pos = n;
            for(int it = 0; it < r; it++) {
                int nextPos = col[x].getR(pos, p);
                if(!nextPos)
                    break;
                row[nextPos].update(x, -1);
                col[x].update(nextPos, -1);
                a[nextPos][x]--;
                pos = nextPos - 1;
            }
        }
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] = max(a[i][j], 0);
            //printf("%d ", a[i][j]);
        }
        //puts("");
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
        }
    }
    
    int ans = 0;
    
    for(int i = p; i <= n; i++) {
        for(int j = p; j <= m; j++) {
            ans = max(ans, dp[i][j] - dp[i - p][j] - dp[i][j - p] + dp[i - p][j - p]);
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
    
}

Compilation message (stderr)

ufo.cpp: In member function 'void tree::update(int, int, int, int, int)':
ufo.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                   ^
ufo.cpp: In member function 'int tree::getL(int, int, int, int, int)':
ufo.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                   ^
ufo.cpp: In member function 'int tree::getR(int, int, int, int, int)':
ufo.cpp:59:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1;
                   ^
ufo.cpp: In function 'int main()':
ufo.cpp:81:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
                                                ^
ufo.cpp:96:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
                            ^
ufo.cpp:106:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &c, &x, &p);
                                       ^

• Subtask 1: 100 / 100