답안 #144293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144293 2019-08-16T14:35:36 Z SamAnd UFO (IZhO14_ufo) C++17
100 / 100
1437 ms 255608 KB
#include <bits/stdc++.h>
using namespace std;

void sar(int**& a, int n, int m)
{
    a = new int*[n + 5];
    for (int i = 0; i < n + 5; ++i)
        a[i] = new int[m + 5];
    for (int i = 0; i < n + 5; ++i)
        for (int j = 0; j < m + 5; ++j)
            a[i][j] = 0;
}

int n, m, r, q, k;
int** a;

int** tt, **ts;

void bil(int*& a, int*& t, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = a[tl];
        return;
    }
    int m = (tl + tr) / 2;
    bil(a, t, tl, m, pos * 2);
    bil(a, t, m + 1, tr, pos * 2 + 1);
    t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
vector<int> v;
void qryl(int*& t, int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        v.push_back(tl);
        return;
    }
    int m = (tl + tr) / 2;
    if (t[pos * 2] >= x)
        qryl(t, tl, m, x, pos * 2);
    if (v.size() > r)
        return;
    if (t[pos * 2 + 1] >= x)
        qryl(t, m + 1, tr, x, pos * 2 + 1);
}
void qryr(int*& t, int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        v.push_back(tl);
        return;
    }
    int m = (tl + tr) / 2;
    if (t[pos * 2 + 1] >= x)
        qryr(t, m + 1, tr, x, pos * 2 + 1);
    if (v.size() > r)
        return;
    if (t[pos * 2] >= x)
        qryr(t, tl, m, x, pos * 2);
}
int qry(int*& t, int tl, int tr, int x, int pos)
{
    if (tl == tr)
        return t[pos];
    int m = (tl + tr) / 2;
    if (x <= m)
        return qry(t, tl, m, x, pos * 2);
    else
        return qry(t, m + 1, tr, x, pos * 2 + 1);
}
void ubd(int*& t, int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        t[pos]--;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(t, tl, m, x, pos * 2);
    else
        ubd(t, m + 1, tr, x, pos * 2 + 1);
    t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("c.in", "r", stdin);
    scanf("%d%d%d%d%d", &n, &m ,&r, &q, &k);
    sar(a, n, m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    sar(tt, n, m * 4);
    for (int i = 1; i <= n; ++i)
        bil(a[i], tt[i], 1, m, 1);
    sar(ts, m, n * 4);
    for (int j = 1; j <= m; ++j)
    {
        int* b;
        b = new int[n + 5];
        for (int i = 0; i < n + 5; ++i)
            b[i] = 0;
        for (int i = 1; i <= n; ++i)
            b[i] = a[i][j];
        bil(b, ts[j], 1, n, 1);
    }
    while (q--)
    {
        char u;
        scanf(" %c", &u);
        if (u == 'W')
        {
            int i, h;
            scanf("%d%d", &i, &h);
            v.clear();
            qryl(tt[i], 1, m, h, 1);
            while (v.size() > r)
                v.pop_back();
            for (int vi = 0; vi < v.size(); ++vi)
            {
                int j = v[vi];
                ubd(tt[i], 1, m, j, 1);
                ubd(ts[j], 1, n, i, 1);
            }
        }
        else if (u == 'E')
        {
            int i, h;
            scanf("%d%d", &i, &h);
            v.clear();
            qryr(tt[i], 1, m, h, 1);
            while (v.size() > r)
                v.pop_back();
            for (int vi = 0; vi < v.size(); ++vi)
            {
                int j = v[vi];
                ubd(tt[i], 1, m, j, 1);
                ubd(ts[j], 1, n, i, 1);
            }
        }
        else if (u == 'N')
        {
            int j, h;
            scanf("%d%d", &j, &h);
            v.clear();
            qryl(ts[j], 1, n, h, 1);
            while (v.size() > r)
                v.pop_back();
            for (int vi = 0; vi < v.size(); ++vi)
            {
                int i = v[vi];
                ubd(tt[i], 1, m, j, 1);
                ubd(ts[j], 1, n, i, 1);
            }
        }
        else
        {
            int j, h;
            scanf("%d%d", &j, &h);
            v.clear();
            qryr(ts[j], 1, n, h, 1);
            while (v.size() > r)
                v.pop_back();
            for (int vi = 0; vi < v.size(); ++vi)
            {
                int i = v[vi];
                ubd(tt[i], 1, m, j, 1);
                ubd(ts[j], 1, n, i, 1);
            }
        }
    }
    long long **p;
    p = new long long*[n + 5];
    for (int i = 0; i < n + 5; ++i)
        p[i] = new long long[m + 5];
    for (int i = 0; i < n + 5; ++i)
        for (int j = 0; j < m + 5; ++j)
            p[i][j] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + qry(tt[i], 1, m, j, 1);
            //cout << qry(tt[i], 1, m, j, 1) << ' ';
        }
        //cout << endl;
    }
    long long ans = 0;
    for (int i = k; i <= n; ++i)
    {
        for (int j = k; j <= m; ++j)
        {
            ans = max(ans, p[i][j] - p[i][j - k] - p[i - k][j] + p[i - k][j - k]);
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

ufo.cpp: In function 'void qryl(int*&, int, int, int, int)':
ufo.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (v.size() > r)
         ~~~~~~~~~^~~
ufo.cpp: In function 'void qryr(int*&, int, int, int, int)':
ufo.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (v.size() > r)
         ~~~~~~~~~^~~
ufo.cpp: In function 'int main()':
ufo.cpp:120:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (v.size() > r)
                    ~~~~~~~~~^~~
ufo.cpp:122:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int vi = 0; vi < v.size(); ++vi)
                              ~~~^~~~~~~~~~
ufo.cpp:135:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (v.size() > r)
                    ~~~~~~~~~^~~
ufo.cpp:137:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int vi = 0; vi < v.size(); ++vi)
                              ~~~^~~~~~~~~~
ufo.cpp:150:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (v.size() > r)
                    ~~~~~~~~~^~~
ufo.cpp:152:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int vi = 0; vi < v.size(); ++vi)
                              ~~~^~~~~~~~~~
ufo.cpp:165:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (v.size() > r)
                    ~~~~~~~~~^~~
ufo.cpp:167:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int vi = 0; vi < v.size(); ++vi)
                              ~~~^~~~~~~~~~
ufo.cpp:91: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, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:95: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:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &u);
         ~~~~~^~~~~~~~~~~
ufo.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &i, &h);
             ~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:132:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &i, &h);
             ~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:147:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &j, &h);
             ~~~~~^~~~~~~~~~~~~~~~
ufo.cpp:162:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &j, &h);
             ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 23 ms 1016 KB Output is correct
5 Correct 116 ms 4444 KB Output is correct
6 Correct 254 ms 26812 KB Output is correct
7 Correct 399 ms 74372 KB Output is correct
8 Correct 322 ms 73336 KB Output is correct
9 Correct 579 ms 61304 KB Output is correct
10 Correct 750 ms 72460 KB Output is correct
11 Correct 545 ms 73556 KB Output is correct
12 Correct 775 ms 72568 KB Output is correct
13 Correct 861 ms 73720 KB Output is correct
14 Correct 753 ms 73592 KB Output is correct
15 Correct 916 ms 74036 KB Output is correct
16 Correct 351 ms 75768 KB Output is correct
17 Correct 1233 ms 74596 KB Output is correct
18 Correct 283 ms 72040 KB Output is correct
19 Correct 513 ms 93304 KB Output is correct
20 Correct 1437 ms 255608 KB Output is correct