Submission #96012

#	Time	Username	Problem	Language	Result	Execution time	Memory
96012		Kastanda	UFO (IZhO14_ufo)	C++11	40 / 100	967 ms	263168 KiB

ufo

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
typedef vector < int > vi;
struct SegTree
{
    int N;
    vi MX, res;
    int k, val, _back, i;
    inline SegTree(int _N = 0)
    {
        N = _N;
        MX.resize((N + 3) << 2);
    }
    inline void Setter(int _i, int _val) {i = _i; val = _val; Set(1, 0, N);}
    inline void Getter(int _k, int _val, int __back) {k = _k; val = _val; _back = __back; res.clear(); Get(1, 0, N);}
    void Set(int id, int l, int r)
    {
        if (r - l < 2)
        {
            MX[id] = val;
            return ;
        }
        if (i < 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 ((int)res.size() == k || MX[id] < val)
            return ;
        if (r - l < 2)
            {res.push_back(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, R;
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));
    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));

    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;
        getchar(); ch = getchar();
        scanf("%d%d", &id, &h);
        id --;
        if (ch == 'N' || ch == 'S')
        {
            cols[id].Getter(R, h, (ch == 'S'));
            for (int &l : cols[id].res)
            {
                A[l][id] --;
                cols[id].Setter(l, A[l][id]);
                rows[l].Setter(id, A[l][id]);
            }
        }
        else
        {
            rows[id].Getter(R, h, (ch == 'E'));
            for (int &l : rows[id].res)
            {
                A[id][l] --;
                rows[id].Setter(l, A[id][l]);
                cols[l].Setter(id, A[id][l]);
            }
        }
    }
    long long 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("%lld\n", Mx);
}

Compilation message (stderr)

ufo.cpp: In member function 'void SegTree::Set(int, int, int)':
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:26:17: note: in expansion of macro 'md'
         if (i < md)
                 ^~
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:27:24: note: in expansion of macro 'md'
             Set(lc, l, md);
                        ^~
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:29:21: note: in expansion of macro 'md'
             Set(rc, md, r);
                     ^~
ufo.cpp: In member function 'void SegTree::Get(int, int, int)':
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:39:24: note: in expansion of macro 'md'
             Get(lc, l, md), Get(rc, md, r);
                        ^~
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:39:37: note: in expansion of macro 'md'
             Get(lc, l, md), Get(rc, md, r);
                                     ^~
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:41:21: note: in expansion of macro 'md'
             Get(rc, md, r), Get(lc, l, md);
                     ^~
ufo.cpp:4:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:41:40: note: in expansion of macro 'md'
             Get(rc, md, r), Get(lc, l, md);
                                        ^~
ufo.cpp: In function 'int main()':
ufo.cpp:51: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:56: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:72: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: 40 / 100