QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402827 | #1286. Ternary String Counting | LCX756 | WA | 2ms | 7192kb | C++14 | 2.5kb | 2024-05-01 16:04:27 | 2024-05-01 16:04:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
#ifdef LCX
#define msg(args...) fprintf(stderr, args)
#else
#define msg(...) void()
#endif
const int maxn = 5010, mod = 1e9 + 7;
int& Dec(int &x, int y) { x -= y; return x < 0 ? x += mod : x; }
int& Inc(int &x, int y) { return Dec(x, mod - y); }
int Diff(int x, int y) { return Dec(x, y); }
int Sum(int x, int y) { return Inc(x, y); }
int n, m;
struct rect {
int xl, xr, yl, yr;
void merge(const rect &p) {
xl = max(p.xl, xl);
yl = max(p.yl, yl);
xr = min(p.xr, xr);
yr = min(p.yr, yr);
}
} lim[maxn];
int f[maxn][maxn], sx[maxn], sy[maxn];
deque <int> pos[maxn];
void add(int j, int k, int v) {
Inc(f[j][k], v), Inc(sx[j], v), Inc(sy[k], v);
}
void work() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
lim[i] = {0, n, 0, n};
for (int i = 1; i <= m; ++i) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if (x == 1) lim[r].merge({0, l - 1, 0, l - 1});
else if (x == 2) lim[r].merge({l, n, 0, l - 1});
else if (x == 3) lim[r].merge({l, n, l, n});
}
for (int i = 0; i <= n; ++i) {
sx[i] = sy[i] = 0;
pos[i].clear();
for (int j = 0; j <= n; ++j)
f[i][j] = 0;
}
add(0, 0, 3);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
int L, R;
if (lim[i].xl <= j && j <= lim[i].xr)
L = lim[i].yl, R = lim[i].yr;
else L = n + 1, R = -1;
while (pos[j].size() && pos[j].front() < L) {
int k = pos[j].front(); pos[j].pop_front();
add(j, k, Diff(0, f[j][k]));
}
while (pos[j].size() && pos[j].back() > R) {
int k = pos[j].back(); pos[j].pop_back();
add(j, k, Diff(0, f[j][k]));
}
}
if (i < n) {
for (int j = 0; j < i; ++j)
pos[i].push_back(j),
add(i, j, Sum(sx[j], sy[j]));
}
}
int ans = 0;
for (int j = 0; j <= n; ++j)
for (int k = 0; k <= n; ++k)
Inc(ans, f[j][k]);
printf("%d\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T --> 0) work();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7192kb
input:
4 1 0 2 0 3 0 5 2 1 3 3 4 5 1
output:
3 9 27 27
result:
wrong answer 4th words differ - expected: '18', found: '27'