답안 #96017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96017 2019-02-05T08:27:58 Z Kastanda UFO (IZhO14_ufo) C++11
100 / 100
1032 ms 173696 KB
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef vector < int > vi;
int R, ts, res[15];
int val, ii, _back;
struct SegTree
{
    int N, * MX;
    inline SegTree(int _N = 0)
    {
        N = _N;
        //MX.resize((N + 3) << 2);
        MX = new int [(N + 3) * 4];
    }
    inline void Setter(int _i, int _val) {ii = _i; val = _val; Set(1, 0, N);}
    inline void Getter(int _val, int __back) {val = _val; _back = __back; ts = 0; Get(1, 0, N);}
    void Set(int id, int l, int r)
    {
        if (id >= ((N + 3) * 4) - 3)
            assert(0);

        if (r - l < 2)
        {
            MX[id] = val;
            return ;
        }
        if (ii < 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 (id >= ((N + 3) * 4) - 3)
            assert(0);

        if (ts >= R || 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;
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;
        cin >> ch;
        //getchar(); ch = getchar();
        scanf("%d%d", &id, &h);
        id --;
        if (ch == 'N' || ch == 'S')
        {
            cols[id].Getter(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(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]);
            }
        }
    }
    int 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("%d\n", Mx);
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:58: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:64: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:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &id, &h);
         ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 16 ms 760 KB Output is correct
5 Correct 79 ms 2680 KB Output is correct
6 Correct 230 ms 17784 KB Output is correct
7 Correct 369 ms 46504 KB Output is correct
8 Correct 308 ms 46640 KB Output is correct
9 Correct 472 ms 38692 KB Output is correct
10 Correct 533 ms 45688 KB Output is correct
11 Correct 421 ms 44252 KB Output is correct
12 Correct 720 ms 45816 KB Output is correct
13 Correct 623 ms 47164 KB Output is correct
14 Correct 651 ms 44324 KB Output is correct
15 Correct 682 ms 44284 KB Output is correct
16 Correct 324 ms 47752 KB Output is correct
17 Correct 1032 ms 46316 KB Output is correct
18 Correct 264 ms 44792 KB Output is correct
19 Correct 391 ms 61320 KB Output is correct
20 Correct 896 ms 173696 KB Output is correct