Submission #96017

#	Time	Username	Problem	Language	Result	Execution time	Memory
96017		Kastanda	UFO (IZhO14_ufo)	C++11	100 / 100	1032 ms	173696 KiB

ufo

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef vector < int > vi;
int R, ts, res[15];
int val, ii, _back;
struct SegTree
{
    int N, * MX;
    inline SegTree(int _N = 0)
    {
        N = _N;
        //MX.resize((N + 3) << 2);
        MX = new int [(N + 3) * 4];
    }
    inline void Setter(int _i, int _val) {ii = _i; val = _val; Set(1, 0, N);}
    inline void Getter(int _val, int __back) {val = _val; _back = __back; ts = 0; Get(1, 0, N);}
    void Set(int id, int l, int r)
    {
        if (id >= ((N + 3) * 4) - 3)
            assert(0);

        if (r - l < 2)
        {
            MX[id] = val;
            return ;
        }
        if (ii < md)
            Set(lc, l, md);
        else
            Set(rc, md, r);
        MX[id] = max(MX[lc], MX[rc]);
    }
    void Get(int id, int l, int r)
    {
        if (id >= ((N + 3) * 4) - 3)
            assert(0);

        if (ts >= R || MX[id] < val)
            return ;
        if (r - l < 2)
            {res[ts ++] = l; return ;}
        if (!_back)
            Get(lc, l, md), Get(rc, md, r);
        else
            Get(rc, md, r), Get(lc, l, md);
        return ;
    }
};
int N, M;
int n, m, q, p_p;
//vector < vi > A;
//vector < SegTree > rows, cols;
int main()
{
    scanf("%d%d%d%d%d", &n, &m, &R, &q, &p_p);
    N = n + 5; M = m + 5;
    //A = vector < vi > (N, vi(M, 0));
    int A[N][M]; // this is bad
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &A[i][j]);
    //rows.resize(N, SegTree(M));
    //cols.resize(M, SegTree(N));
    SegTree rows[N];
    SegTree cols[M];
    for (int i = 0; i < n; i++)
        rows[i] = SegTree(m);
    for (int i = 0; i < m; i++)
        cols[i] = SegTree(n);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            rows[i].Setter(j, A[i][j]);
            cols[j].Setter(i, A[i][j]);
        }

    for (int i = 1; i <= q; i++)
    {
        int id, h;
        char ch;
        cin >> ch;
        //getchar(); ch = getchar();
        scanf("%d%d", &id, &h);
        id --;
        if (ch == 'N' || ch == 'S')
        {
            cols[id].Getter(h, (ch == 'S'));
            for (int j = 0; j < ts; j++)
            {
                int &l = res[j];
                A[l][id] --;
                cols[id].Setter(l, A[l][id]);
                rows[l].Setter(id, A[l][id]);
            }
        }
        else
        {
            rows[id].Getter(h, (ch == 'E'));
            for (int j = 0; j < ts; j++)
            {
                int &l = res[j];
                A[id][l] --;
                rows[id].Setter(l, A[id][l]);
                cols[l].Setter(id, A[id][l]);
            }
        }
    }
    int sum = 0, Mx = 0;
    for (int i = 0; i + p_p <= n; i++)
    {
        sum = 0;
        for (int j = 0; j < m; j++)
        {
            for (int h = 0; h < p_p; h++)
                sum += A[i + h][j];
            if (j >= p_p)
                for (int h = 0; h < p_p; h++)
                    sum -= A[i + h][j - p_p];
            Mx = max(Mx, sum);
        }
    }
    return !printf("%d\n", Mx);
}

Compilation message (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:58:10: 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, &q, &p_p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &id, &h);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100