QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402827#1286. Ternary String CountingLCX756WA 2ms7192kbC++142.5kb2024-05-01 16:04:272024-05-01 16:04:28

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 16:04:28]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7192kb
  • [2024-05-01 16:04:27]
  • 提交

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'