Submission #133870

#	Time	Username	Problem	Language	Result	Execution time	Memory
133870		Kastanda	UFO (IZhO14_ufo)	C++11	100 / 100	1016 ms	183288 KiB

ufo

// ItnoE
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
int R, ts, val, ii, ret[11];
struct Tree
{
    int N, * MX;
    inline Tree(int _N = 0)
    {
        N = _N;
        MX = new int [N + 3 << 2];
    }
    inline void Setter(int _ii, int _val)
    {
        ii = _ii;
        val = _val;
        Set(1, 1, N + 1);
    }
    inline void Getter(int _val, int d)
    {
        ts = 0;
        val = _val;
        if (d == 0)
            GetPref(1, 1, N + 1);
        else
            GetSuff(1, 1, N + 1);
    }
    void Set(int id, int l, int r)
    {
        if (r - l < 2)
            return void(MX[id] = val);
        if (ii < md)
            Set(lc, l, md);
        else
            Set(rc, md, r);
        MX[id] = max(MX[lc], MX[rc]);
    }
    void GetPref(int id, int l, int r)
    {
        if (MX[id] < val || ts >= R)
            return ;
        if (r - l < 2)
            return void(ret[ts ++] = l);
        GetPref(lc, l, md);
        GetPref(rc, md, r);
    }
    void GetSuff(int id, int l, int r)
    {
        if (MX[id] < val || ts >= R)
            return ;
        if (r - l < 2)
            return void(ret[ts ++] = l);
        GetSuff(rc, md, r);
        GetSuff(lc, l, md);
    }
};
int main()
{
    int n, m, q, p;
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> R >> q >> p;
    int A[n + 3][m + 3];
    memset(A, 0, sizeof(A));
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> A[i][j];
    Tree rows[n + 3], cols[m + 3];
    for (int i = 1; i <= n; i ++)
        rows[i] = Tree(m);
    for (int i = 1; i <= m; i ++)
        cols[i] = Tree(n);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            rows[i].Setter(j, A[i][j]);
            cols[j].Setter(i, A[i][j]);
        }
    for (; q; q --)
    {
        char ch;
        int id, h;
        cin >> ch >> id >> h;
        if (ch == 'W' || ch == 'E')
        {
            rows[id].Getter(h, ch == 'E');
            for (int i = 0; i < ts; i ++)
            {
                A[id][ret[i]] --;
                rows[id].Setter(ret[i], A[id][ret[i]]);
                cols[ret[i]].Setter(id, A[id][ret[i]]);
            }
        }
        else
        {
            cols[id].Getter(h, ch == 'S');
            for (int i = 0; i < ts; i ++)
            {
                A[ret[i]][id] --;
                rows[ret[i]].Setter(id, A[ret[i]][id]);
                cols[id].Setter(ret[i], A[ret[i]][id]);
            }
        }
    }
    int Mx = 0;
    for (int i = p; i <= n; i ++)
        for (int j = p; j <= m; j ++)
        {
            int SM = 0;
            for (int a = i - p + 1; a <= i; a ++)
                for (int b = j - p + 1; b <= j; b ++)
                    SM += A[a][b];
            Mx = max(Mx, SM);
        }
    return !printf("%d\n", Mx);
}

Compilation message (stderr)

ufo.cpp: In constructor 'Tree::Tree(int)':
ufo.cpp:14:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
         MX = new int [N + 3 << 2];
                       ~~^~~
ufo.cpp: In member function 'void Tree::Set(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:35:18: note: in expansion of macro 'md'
         if (ii < md)
                  ^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:36:24: note: in expansion of macro 'md'
             Set(lc, l, md);
                        ^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:38:21: note: in expansion of macro 'md'
             Set(rc, md, r);
                     ^~
ufo.cpp: In member function 'void Tree::GetPref(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:47:24: note: in expansion of macro 'md'
         GetPref(lc, l, md);
                        ^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:48:21: note: in expansion of macro 'md'
         GetPref(rc, md, r);
                     ^~
ufo.cpp: In member function 'void Tree::GetSuff(int, int, int)':
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:56:21: note: in expansion of macro 'md'
         GetSuff(rc, md, r);
                     ^~
ufo.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
ufo.cpp:57:24: note: in expansion of macro 'md'
         GetSuff(lc, l, md);
                        ^~

• Subtask 1: 100 / 100