QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#495794#9155. 集合superguymj100 ✓1427ms77736kbC++205.2kb2024-07-27 23:44:172024-07-27 23:44:17

Judging History

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

  • [2024-07-27 23:44:17]
  • 评测
  • 测评结果:100
  • 用时:1427ms
  • 内存:77736kb
  • [2024-07-27 23:44:17]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;

using i64 = long long;
template<int P>
struct MInt {
    int x;
    MInt() : x{} {}
    MInt(i64 x) : x{norm(x % getMod())} {}
     
    static int Mod;
    static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    static void setMod(int Mod_) {
        Mod = Mod_;
    }
    int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    int val() const {
        return x;
    }
    explicit operator int() const {
        return x;
    }
    MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<>
int MInt<0>::Mod = 1;
 
template<int P1, int P2>
struct Hash {
    MInt<P1> x;
    MInt<P2> y;
    Hash() : x{0}, y{0} {}
    Hash(int x, int y) : x{x}, y{y} {}
    Hash(MInt<P1> x, MInt<P2> y) : x{x}, y{y} {}

    friend Hash operator+(Hash lhs, Hash rhs) {
        return Hash(lhs.x + rhs.x, lhs.y + rhs.y);
    }
    friend Hash operator-(Hash lhs, Hash rhs) {
        return Hash(lhs.x - rhs.x, lhs.y - rhs.y);
    }
    friend Hash operator*(Hash lhs, Hash rhs) {
        return Hash(lhs.x * rhs.x, lhs.y * rhs.y);
    }
    Hash &operator+=(Hash rhs) & {
        x += rhs.x;
        y += rhs.y;
        return *this;
    }
    Hash &operator-=(Hash rhs) & {
        x -= rhs.x;
        y -= rhs.y;
        return *this;
    }
    Hash &operator*=(Hash rhs) & {
        x *= rhs.x;
        y *= rhs.y;
        return *this;
    }
    friend bool operator==(Hash lhs, Hash rhs) {
        return lhs.x == rhs.x && lhs.y == rhs.y; 
    }
    friend bool operator!=(Hash lhs, Hash rhs) {
        return lhs.x != rhs.x || lhs.y != rhs.y; 
    }
    bool operator<(const Hash &t) const {
        return int(x) == int(t.x) ? int(y) < int(t.y) : int(x) < int(t.x);
    }
    
} ;

constexpr int P1 = 1000000007, P2 = 1000000009;
using H = Hash<P1, P2>;
const H base = H(19260817, 998244353);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int, 3>> a(n), b(n);
    rep(i,0,n-1)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        rep(j,0,2) --a[i][j];
    }
    rep(i,0,n-1)
    {
        cin >> b[i][0] >> b[i][1] >> b[i][2];
        rep(j,0,2) --b[i][j];
    }

    vector<H> pw(n);
    pw[0] = H(1, 1);
    rep(i,1,n-1) pw[i] = pw[i - 1] * base;

    vector<H> A(m), B(m);
    map<H, int> cnt;
    int tot = 0;
    int p = 0;

    auto ins = [&](H h, int c)
    {
        int &val = cnt[h];
        if(val) --tot;
        val += c;
        if(val) ++tot;
    };

    vector<int> lst(n);

    rep(i,0,n-1)
    {
        for(auto j : a[i])
        {
            ins(A[j], -1);
            A[j] += pw[i];
            ins(A[j], 1);
        }
        for(auto j : b[i])
        {
            ins(B[j], 1);
            B[j] += pw[i];
            ins(B[j], -1);
        }
        while(tot)
        {
            for(auto j : a[p])
            {
                ins(A[j], -1);
                A[j] -= pw[p];
                ins(A[j], 1);
            }
            for(auto j : b[p])
            {
                ins(B[j], 1);
                B[j] -= pw[p];
                ins(B[j], -1);
            }
            p++;
        }
        lst[i] = p;
    }

    while(q--)
    {
        int l, r;
        cin >> l >> r;
        --l, --r;
        if(lst[r] <= l)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 3628kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 3568kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 3560kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 3824kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 3620kb

Pretest #6:

score: 5
Accepted
time: 0ms
memory: 3824kb

Pretest #7:

score: 5
Accepted
time: 1ms
memory: 3812kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 3560kb

Pretest #9:

score: 5
Accepted
time: 16ms
memory: 3684kb

Pretest #10:

score: 5
Accepted
time: 20ms
memory: 3560kb

Pretest #11:

score: 5
Accepted
time: 1246ms
memory: 77736kb

Pretest #12:

score: 5
Accepted
time: 1222ms
memory: 73000kb

Pretest #13:

score: 5
Accepted
time: 6ms
memory: 4532kb

Pretest #14:

score: 5
Accepted
time: 5ms
memory: 4204kb

Pretest #15:

score: 5
Accepted
time: 107ms
memory: 4332kb

Pretest #16:

score: 5
Accepted
time: 101ms
memory: 4556kb

Pretest #17:

score: 5
Accepted
time: 76ms
memory: 10452kb

Pretest #18:

score: 5
Accepted
time: 64ms
memory: 10560kb

Pretest #19:

score: 5
Accepted
time: 1378ms
memory: 74764kb

Pretest #20:

score: 5
Accepted
time: 1112ms
memory: 74744kb

Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 3828kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 3632kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 3632kb

Test #4:

score: 5
Accepted
time: 0ms
memory: 3636kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 3632kb

Test #6:

score: 5
Accepted
time: 0ms
memory: 3796kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 3848kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 3620kb

Test #9:

score: 5
Accepted
time: 20ms
memory: 3680kb

Test #10:

score: 5
Accepted
time: 21ms
memory: 3852kb

Test #11:

score: 5
Accepted
time: 1322ms
memory: 73564kb

Test #12:

score: 5
Accepted
time: 1347ms
memory: 69348kb

Test #13:

score: 5
Accepted
time: 6ms
memory: 4268kb

Test #14:

score: 5
Accepted
time: 5ms
memory: 4316kb

Test #15:

score: 5
Accepted
time: 108ms
memory: 4300kb

Test #16:

score: 5
Accepted
time: 101ms
memory: 4336kb

Test #17:

score: 5
Accepted
time: 72ms
memory: 10752kb

Test #18:

score: 5
Accepted
time: 65ms
memory: 10296kb

Test #19:

score: 5
Accepted
time: 1427ms
memory: 72528kb

Test #20:

score: 5
Accepted
time: 1233ms
memory: 75616kb

Extra Test:

score: 0
Extra Test Passed