Submission #96012

# Submission time Handle Problem Language Result Execution time Memory
96012 2019-02-05T08:05:11 Z Kastanda UFO (IZhO14_ufo) C++11
40 / 100
967 ms 263168 KB
#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

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);
         ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 2 ms 256 KB Output is correct
3 Runtime error 3 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 15 ms 988 KB Output is correct
5 Correct 77 ms 4504 KB Output is correct
6 Correct 241 ms 21512 KB Output is correct
7 Runtime error 388 ms 138740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 368 ms 135120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 376 ms 104268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 324 ms 135032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 433 ms 74956 KB Output is correct
12 Runtime error 327 ms 135064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 278 ms 143836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 581 ms 75212 KB Output is correct
15 Correct 685 ms 71764 KB Output is correct
16 Runtime error 315 ms 144716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 967 ms 80440 KB Output is correct
18 Runtime error 273 ms 145444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 363 ms 196904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 363 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)