| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 393436 |
2021-04-23T12:34:06 Z |
patrikpavic2 |
UFO (IZhO14_ufo) |
C++17 |
|
2000 ms |
231640 KB |
#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;
typedef vector < int > vi;
const int N = 1e6 + 500;
struct tournament{
vi T;
int off;
void build(vector < int > &v){
for(off = 1; (int)v.size() > off; off <<= 1);
T.resize(2 * off);
for(int i = 0;i < (int)v.size();i++)
T[off + i] = v[i];
for(int i = off - 1; i ; i--)
T[i] = max(T[2 * i], T[2 * i + 1]);
}
void update(int i){
T[off + i]--;
for(i = (i + off) / 2 ; i ; i--)
T[i] = max(T[2 * i], T[2 * i + 1]);
}
vi ans;
void nadi(int i, int x, int kol, bool L){
if(i >= off) {
ans.PB(i - off);
return;
}
if(T[2 * i] >= x && (int)ans.size() < kol && L)
nadi(2 * i, x, kol, L);
if(T[2 * i + 1] >= x && (int)ans.size() < kol)
nadi(2 * i + 1, x, kol, L);
if(T[2 * i] >= x && (int)ans.size() < kol && !L)
nadi(2 * i, x, kol, L);
}
};
vi vR[N], vC[N];
tournament R[N], C[N];
int n, m, r, q, p;
int main(){
scanf("%d%d%d%d%d", &n, &m, &r, &q, &p);
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
int x; scanf("%d", &x);
vR[i].PB(x); vC[j].PB(x);
}
}
for(int i = 0;i < n;i++)
R[i].build(vR[i]);
for(int j = 0;j < m;j++)
C[j].build(vC[j]);
for(int i = 0;i < q;i++){
char c; int pos, h; scanf(" %c%d%d", &c, &pos, &h);
pos--;
if(c == 'N' || c == 'S'){
C[pos].nadi(1, h, r, c == 'N');
for(int x : C[pos].ans)
C[pos].update(x), R[x].update(pos);
C[pos].ans.clear();
}
else{
R[pos].nadi(1, h, r, c == 'W');
for(int x : R[pos].ans)
R[pos].update(x), C[x].update(pos);
R[pos].ans.clear();
}
}
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
vR[i][j] = R[i].T[R[i].off + j];
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
vR[i][j] += (i ? vR[i - 1][j] : 0) + (j ? vR[i][j - 1] : 0) - (i && j ? vR[i - 1][j - 1] : 0);
int sol = 0;
for(int i = 0;i + p <= n;i++)
for(int j = 0;j + p <= m;j++)
sol = max(sol, vR[i + p - 1][j + p - 1] - (i ? vR[i - 1][j + p - 1] : 0)
- (j ? vR[i + p - 1][j - 1] : 0) + (i && j ? vR[i - 1][j - 1] : 0));
printf("%d\n", sol);
return 0;
}
Compilation message
ufo.cpp: In function 'int main()':
ufo.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
49 | scanf("%d%d%d%d%d", &n, &m, &r, &q, &p);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:52:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
ufo.cpp:61:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | char c; int pos, h; scanf(" %c%d%d", &c, &pos, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
156868 KB |
Output is correct |
| 2 |
Correct |
83 ms |
156828 KB |
Output is correct |
| 3 |
Correct |
85 ms |
156880 KB |
Output is correct |
| 4 |
Correct |
122 ms |
157148 KB |
Output is correct |
| 5 |
Execution timed out |
2082 ms |
159180 KB |
Time limit exceeded |
| 6 |
Correct |
716 ms |
173848 KB |
Output is correct |
| 7 |
Execution timed out |
2105 ms |
193244 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2087 ms |
192960 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2083 ms |
191764 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2070 ms |
193264 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2099 ms |
184144 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2090 ms |
193228 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2075 ms |
193360 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2084 ms |
184248 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2099 ms |
193040 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2088 ms |
183964 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2053 ms |
193344 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2101 ms |
182540 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2080 ms |
196116 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2098 ms |
231640 KB |
Time limit exceeded |
