Submission #226282

#	Time	Username	Problem	Language	Result	Execution time	Memory
226282		emil_physmath	UFO (IZhO14_ufo)	C++17	75 / 100	2066 ms	102700 KiB

ufo

#include <iostream>
#include <vector>
using namespace std;

int shots;
int n, m;
vector<vector<int> > a;
vector<int> tcol[1000'000], trow[1000'000];

void Shoot(const vector<int>& t, int v, int vl, int vr, int hei, int dir, vector<int>& ans)
{
    if (ans.size() == shots) return;
    if (t[v] < hei) return;
    if (vl == vr)
    {
        ans.push_back(vr);
        return;
    }
    int vm = (vl + vr) / 2;
    if (dir == 1)
    {
        Shoot(t, v * 2, vl, vm, hei, dir, ans);
        Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
    }
    else
    {
        Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
        Shoot(t, v * 2, vl, vm, hei, dir, ans);
    }
}
void Add(vector<int>& t, int v, int vl, int vr, int i, int val)
{
    if (vl == vr)
    {
        t[v] += val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (i <= vm) Add(t, v * 2, vl, vm, i, val);
    else Add(t, v * 2 + 1, vm + 1, vr, i, val);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void SetRow(int i, int v, int vl, int vr)
{
    if (vl == vr)
    {
        a[i][vr] = trow[i][v];
        return;
    }
    int vm = (vl + vr) / 2;
    SetRow(i, v * 2, vl, vm);
    SetRow(i, v * 2 + 1, vm + 1, vr);
}
int main()
{
    int qnum, anpetq;
    cin >> n >> m >> shots >> qnum >> anpetq;
    a.resize(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        trow[i].resize(4 * m);
    for (int j = 0; j < m; ++j)
        tcol[j].resize(4 * n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            cin >> a[i][j];
            Add(trow[i], 1, 0, m - 1, j, a[i][j]);
            Add(tcol[j], 1, 0, n - 1, i, a[i][j]);
        }
    while (qnum--)
    {
        char dir;
        int i, hei;
        cin >> dir >> i >> hei;
        int j = --i;
        vector<int> col;
        vector<int> row;
        if (dir == 'W')
            Shoot(trow[i], 1, 0, m - 1, hei, 1, col);
        else if (dir == 'E')
            Shoot(trow[i], 1, 0, m - 1, hei, -1, col);
        else if (dir == 'N')
            Shoot(tcol[j], 1, 0, n - 1, hei, 1, row);
        else // 'S'
            Shoot(tcol[j], 1, 0, n - 1, hei, -1, row);
        if (dir == 'W' || dir == 'E')
            for (int j: col)
            {
                Add(trow[i], 1, 0, m - 1, j, -1);
                Add(tcol[j], 1, 0, n - 1, i, -1);
            }
        else
            for (int i: row)
            {
                Add(trow[i], 1, 0, m - 1, j, -1);
                Add(tcol[j], 1, 0, n - 1, i, -1);
            }
    }
    for (int i = 0; i < n; ++i)
        SetRow(i, 1, 0, m - 1);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
#ifdef MANSON
            cerr << a[i][j] << ' ';
#endif
            if (i + anpetq >= n || j + anpetq >= m) continue;
            int cur = 0;
            for (int di = 0; di < anpetq; ++di)
                for (int dj = 0; dj < anpetq; ++dj)
                    cur += a[i + di][j + dj];
            ans = max(ans, cur);
        }
#ifdef MANSON
        cerr << '\n';
#endif
    }
    cout << ans;
}

Compilation message (stderr)

ufo.cpp: In function 'void Shoot(const std::vector<int>&, int, int, int, int, int, std::vector<int>&)':
ufo.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ans.size() == shots) return;
         ~~~~~~~~~~~^~~~~~~~

• Subtask 1: 75 / 100