oj.uz

Submission #96014

# Submission time Handle Problem Language Result Execution time Memory
96014 2019-02-05T08:12:23 Z Kastanda UFO (IZhO14_ufo) C++11
55 / 100
 849 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;
int ts, res[15];
struct SegTree
{
    int N, * MX;
    int k, val, _back, i;
    inline SegTree(int _N = 0)
    {
        N = _N;
        //MX.resize((N + 3) << 2);
        MX = new int [(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; ts = 0; 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 (ts == k || 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, 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));
    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;
        getchar(); ch = getchar();
        scanf("%d%d", &id, &h);
        id --;
        if (ch == 'N' || ch == 'S')
        {
            cols[id].Getter(R, 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(R, 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]);
            }
        }
    }
    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:27: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:28: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:30: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:40: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:40: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:42: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:42:40: note: in expansion of macro 'md'
             Get(rc, md, r), Get(lc, l, md);
                                        ^~
ufo.cpp: In function 'int main()':
ufo.cpp:52: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:58: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:80: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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Correct 15 ms 888 KB Output is correct
5 Correct 75 ms 3448 KB Output is correct
6 Correct 211 ms 18232 KB Output is correct
7 Runtime error 321 ms 107392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 262 ms 107320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 288 ms 83984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 294 ms 107356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 464 ms 55928 KB Output is correct
12 Runtime error 353 ms 107680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 332 ms 57332 KB Output is correct
14 Correct 509 ms 56072 KB Output is correct
15 Correct 564 ms 54064 KB Output is correct
16 Runtime error 256 ms 111096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 849 ms 55928 KB Output is correct
18 Correct 242 ms 56568 KB Output is correct
19 Runtime error 369 ms 154328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 521 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)