oj.uz

답안 #133870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133870 2019-07-21T15:49:03 Z Kastanda UFO (IZhO14_ufo) C++11
100 / 100
 1016 ms 183288 KB 
// 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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 21 ms 760 KB Output is correct
5 Correct 91 ms 2796 KB Output is correct
6 Correct 243 ms 17784 KB Output is correct
7 Correct 369 ms 47736 KB Output is correct
8 Correct 298 ms 47756 KB Output is correct
9 Correct 503 ms 39288 KB Output is correct
10 Correct 558 ms 46948 KB Output is correct
11 Correct 429 ms 46840 KB Output is correct
12 Correct 583 ms 46880 KB Output is correct
13 Correct 651 ms 47776 KB Output is correct
14 Correct 553 ms 46884 KB Output is correct
15 Correct 667 ms 47608 KB Output is correct
16 Correct 308 ms 49016 KB Output is correct
17 Correct 959 ms 48636 KB Output is correct
18 Correct 280 ms 45916 KB Output is correct
19 Correct 416 ms 63736 KB Output is correct
20 Correct 1016 ms 183288 KB Output is correct