QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#571590	#9356. LRU Algorithm	ucup-team004^#	WA	206ms	3876kb	C++20	4.6kb	2024-09-18 00:54:38	2024-09-18 00:54:40

Judging History

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

[2024-09-26 19:14:31]
hack成功，自动添加数据
(/hack/913)

[2024-09-26 19:12:47]
hack成功，自动添加数据
(/hack/912)

[2024-09-18 00:54:40]
评测

测评结果：WA
用时：206ms
内存：3876kb

查看

[2024-09-18 00:54:38]
提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// TODO: Dynamic ModInt

template<typename T>
constexpr T power(T a, u64 b) {
    T res {1};
    for (; b != 0; b /= 2, a *= a) {
        if (b % 2 == 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return 1ULL * a * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

template<typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase {
public:
    constexpr ModIntBase() : x {0} {}
    
    template<typename T>
    requires std::integral<T>
    constexpr ModIntBase(T x_) : x {norm(x_ % T {P})} {}
    
    constexpr static U norm(U x) {
        if ((x >> (8 * sizeof(U) - 1) & 1) == 1) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = norm(P - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, P - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<P>(x, rhs.val());
        return *this;
    }
    
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() != rhs.val();
    }
    
    friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() < rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;

template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

constexpr u64 P = u64(1E18) + 9;
using Z = ModInt64<P>;

constexpr Z B = 1145141LL;

void solve() {
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n), nxt(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    std::vector<int> lst(n, n);
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    
    std::vector<std::vector<std::pair<Z, int>>> qry(n + 1);
    for (int i = 0; i < q; i++) {
        int m;
        std::cin >> m;
        
        Z h = 0ULL;
        for (int j = 0; j < m; j++) {
            int x;
            std::cin >> x;
            if (x > 0) {
                h = h * B + u64(x);
            }
        }
        qry[m].emplace_back(h, i);
    }
    
    std::vector<bool> ans(q);
    
    std::vector<int> cur(n);
    std::iota(cur.begin(), cur.end(), 0);
    std::vector<Z> f(n);
    for (int m = 1; m <= n; m++) {
        for (int i = 0; i < n; i++) {
            int &j = cur[i];
            while (j >= 0) {
                if (nxt[j] > i) {
                    f[i] = f[i] * B + u64(a[j] + 1);
                    j--;
                    break;
                }
                j--;
            }
        }
        for (auto [h, i] : qry[m]) {
            ans[i] = (std::find(f.begin(), f.end(), h) != f.end());
        }
    }
    
    for (int i = 0; i < q; i++) {
        std::cout << (ans[i] ? "Yes" : "No") << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3876kb

input:

1
7 5
4 3 4 2 3 1 4
1 4
2 2 3
3 3 2 1
4 4 1 3 2
4 3 4 0 0

output:

Yes
No
No
Yes
Yes

result:

ok 5 lines

Test #2:

score: -100

Wrong Answer

time: 206ms

memory: 3852kb

input:

105
50 10
23 30 34 20 27 11 21 29 12 7 21 42 45 48 8 15 6 16 19 35 16 14 29 11 31 18 22 4 45 22 14 4 13 40 43 48 27 15 15 15 15 10 15 11 31 37 34 34 50 14
1 25
2 23 6
3 29 21 11
4 12 29 18 39
5 29 21 11 27 20
6 21 10 9 3 34 14
7 49 36 36 43 50 50 35
8 12 29 21 11 27 20 34 30
9 11 27 20 34 30 23 0 0 ...

output:

No
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes...

result:

wrong answer 44th lines differ - expected: 'Yes', found: 'No'