Submission #144293

#TimeUsernameProblemLanguageResultExecution timeMemory
144293SamAndUFO (IZhO14_ufo)C++17
100 / 100
1437 ms255608 KiB
#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 (stderr)

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);
             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...