QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#74411 | #5414. Stop, Yesterday Please No More | magicduck# | WA | 2ms | 3644kb | C++14 | 2.7kb | 2023-02-01 13:26:42 | 2023-02-01 13:26:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
int R = 1; F = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
F *= R;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 2e3 + 10, M = 1e6 + 10;
char s[M]; int n, m, k, res[N][N]; vector<int> v[N];
struct BIT {
int c[N];
void add(int x) {
for(; x <= m * 2 - 1; x += (x & -x)) c[x]++;
}
int qry(int x) {
int r = 0;
for(; x; x -= (x & -x))
r += c[x];
return r;
}
int qry(int l, int r) {
return qry(r) - qry(l - 1);
}
}tr;
struct mat {
int l, r, x, y, op;
}; vector<mat> g[N];
int main() {
//file("");
int T; read(T);
while(T--) {
read(n), read(m), read(k);
for(int i = 0; i <= 2 * n; i++) v[i].clear(), g[i].clear();
scanf("%s", s + 1); int p = strlen(s + 1);
int X = 0, Y = 0, xl = 1, xr = n, yl = 1, yr = m;
v[n].emplace_back(m);
for(int i = 1; i <= p; i++) {
if(s[i] == 'U') X--, xl = max(xl, -X + 1);
else if(s[i] == 'D') X++, xr = min(xr, n - X);
else if(s[i] == 'L') Y--, yl = max(yl, -Y + 1);
else Y++, yr = min(yr, m - Y);
if(X > -n && X < n && Y > -m && Y < m)
v[n - X].emplace_back(m - Y);
}
if(xl > xr || yl > yr) {
if(k == 0) cout << n * m << '\n';
else puts("0");
continue;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
int l = xl - i + n, r = xr - i + n;
int ll = yl - j + m, rr = yr - j + m;
g[l - 1].push_back((mat){ll, rr, i, j, -1});
g[r].push_back((mat){ll, rr, i, j, 1});
res[i][j] = 0;
}
for(int i = 1; i <= 2 * m - 1; i++) tr.c[i] = 0;
for(int i = 1; i <= 2 * n; i++) {
for(int j : v[i]) tr.add(j);
for(auto j : g[i])
res[j.x][j.y] += tr.qry(j.l, j.r) * j.op;
}
int ans = 0; const int sum = (xr - xl + 1) * (yr - yl + 1);
cout << sum << '\n';
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(sum - res[i][j] == k) ans++;
cout << ans << '\n';
}
#ifdef _MagicDuck
fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3644kb
input:
3 4 5 3 ULDDRR 4 5 0 UUUUUUU 4 5 10 UUUUUUU
output:
6 2 20 0
result:
wrong answer 1st numbers differ - expected: '2', found: '6'