QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601778#9155. 集合Hunster#100 ✓1239ms98836kbC++205.7kb2024-09-30 13:01:192024-09-30 13:01:20

Judging History

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

  • [2024-09-30 13:01:20]
  • 评测
  • 测评结果:100
  • 用时:1239ms
  • 内存:98836kb
  • [2024-09-30 13:01:19]
  • 提交

answer

#include <bits/stdc++.h>

namespace IO {
    #ifdef _DEBUG
    constexpr int MAX_SIZE = 1;
    #else
    constexpr int MAX_SIZE = 1 << 20;
    #endif
    class Reader {
    private:
        FILE *file;
        char buff[MAX_SIZE], *p1, *p2;
        int getchar() {
            if (p1 == p2) p2 = (p1 = buff) + fread(buff, 1, MAX_SIZE, file);
            return p1 == p2 ? EOF : *p1++;
        }
    public:
        Reader(FILE *_file) {
            file = _file;
            p1 = p2 = buff;
        }
        Reader(const char* file_dir) {
            file = std::fopen(file_dir, "r");
            p1 = p2 = buff;
        }
        void read() {}
        template<typename... Args>
        void read(int &x, Args &...other) {
            int f, ch;
            x = f = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            if (f) x = -x;
            read(other...);
        }
        template<typename... Args>
        void read(long long &x, Args &...other) {
            int f, ch;
            x = f = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            if (f) x = -x;
            read(other...);
        }
        template<typename... Args>
        void read(__int128 &x, Args &...other) {
            int f, ch;
            x = f = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            if (f) x = -x;
            read(other...);
        }
       template<typename... Args>
        void read(unsigned int &x, Args &...other) {
            int ch;
            x = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) ;
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            read(other...);
        }
        template<typename... Args>
        void read(unsigned long long &x, Args &...other) {
            int ch;
            x = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) ;
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            read(other...);
        }
        template<typename... Args>
        void read(unsigned __int128 &x, Args &...other) {
            int ch;
            x = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) ;
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            read(other...);
        }
        template<typename... Args>
        void read(double &x, Args &...other) {
            int f, ch;
            x = f = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            if (ch == '.') {
                double e = 1;
                for (ch = getchar(); isdigit(ch); ch = getchar())
                    x += (ch ^ 48) * (e *= .1);
            }
            if (f) x = -x;
            read(other...);
        }
        template<typename... Args>
        void read(char &ch, Args &...other) {
            ch = getchar();
            while (!isgraph(ch)) ch = getchar();
            read(other...);
        }
        template<typename... Args>
        void read(std::string &s, Args &...other) {
            char ch;
            s = "";
            ch = getchar();
            for (; !isgraph(ch);) ch = getchar();
            for (; isgraph(ch); ch = getchar()) s += ch;
            read(other...);
        }
        template<typename... Args>
        void read(long double &x, Args &...other) {
            int f, ch;
            x = f = 0;
            ch = getchar();
            for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
            for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
            if (ch == '.') {
                long double e = 1;
                for (ch = getchar(); isdigit(ch); ch = getchar())
                    x += (ch ^ 48) * (e *= .1);
            }
            if (f) x = -x;
            read(other...);
        }
        void read(char* s) {
            char ch;
            ch = getchar();
            while (!isgraph(ch)) ch = getchar();
            for (; isgraph(ch); ch = getchar()) *s++ = ch;
            *s = 0;
        }
    };
}
IO::Reader reader(stdin);

using ULL = unsigned long long;

constexpr int N = 200005, Q = 1000006;

std::mt19937_64 rng((std::random_device())());

int n, m, q;
int a[N][3], b[N][3];
ULL val[N], ha[3 * N], hb[3 * N];
int cnt = 0;
std::map<ULL, int> map;
void add(int i, int v) {
    for (int o : {0, 1, 2}) {
        cnt -= --map[ha[a[i][o]]] == 0;
        ha[a[i][o]] += v * val[i];
        cnt += map[ha[a[i][o]]]++ == 0;
        cnt += map[hb[b[i][o]]]++ == 0;
        hb[b[i][o]] += v * val[i];
        cnt -= --map[hb[b[i][o]]] == 0;
    }
}
int ans[Q];
std::vector<std::pair<int, int>> e[N];

int main() {
    reader.read(n, m, q);
    for (int i = 1; i <= n; i++) reader.read(a[i][0], a[i][1], a[i][2]);
    for (int i = 1; i <= n; i++) reader.read(b[i][0], b[i][1], b[i][2]);
    for (int i = 1; i <= n; i++) val[i] = rng();
    for (int i = 1; i <= q; i++) {
        int l, r;
        reader.read(l, r);
        e[r].push_back({l, i});
    }
    for (int i = 1, j = 1; i <= n; i++) {
        add(i, 1);
        while (j <= i && cnt) add(j++, -1);
        for (auto [l, id] : e[i]) ans[id] = l >= j;
    }
    for (int i = 1; i <= q; i++) puts(ans[i] ? "Yes" : "No");
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 15912kb

Pretest #5:

score: 5
Accepted
time: 2ms
memory: 15912kb

Pretest #6:

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

Pretest #7:

score: 5
Accepted
time: 2ms
memory: 13832kb

Pretest #8:

score: 5
Accepted
time: 2ms
memory: 16172kb

Pretest #9:

score: 5
Accepted
time: 3ms
memory: 18072kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 1104ms
memory: 91944kb

Pretest #12:

score: 5
Accepted
time: 965ms
memory: 86120kb

Pretest #13:

score: 5
Accepted
time: 3ms
memory: 12512kb

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 31ms
memory: 29356kb

Pretest #16:

score: 5
Accepted
time: 35ms
memory: 29536kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 50ms
memory: 22540kb

Pretest #19:

score: 5
Accepted
time: 1239ms
memory: 98812kb

Pretest #20:

score: 5
Accepted
time: 1017ms
memory: 97948kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

score: 5
Accepted
time: 2ms
memory: 15820kb

Test #6:

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

Test #7:

score: 5
Accepted
time: 2ms
memory: 15904kb

Test #8:

score: 5
Accepted
time: 2ms
memory: 15872kb

Test #9:

score: 5
Accepted
time: 3ms
memory: 18016kb

Test #10:

score: 5
Accepted
time: 7ms
memory: 18120kb

Test #11:

score: 5
Accepted
time: 1125ms
memory: 86764kb

Test #12:

score: 5
Accepted
time: 976ms
memory: 83596kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 12712kb

Test #14:

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

Test #15:

score: 5
Accepted
time: 43ms
memory: 29384kb

Test #16:

score: 5
Accepted
time: 28ms
memory: 29652kb

Test #17:

score: 5
Accepted
time: 61ms
memory: 23236kb

Test #18:

score: 5
Accepted
time: 41ms
memory: 20640kb

Test #19:

score: 5
Accepted
time: 1121ms
memory: 96600kb

Test #20:

score: 5
Accepted
time: 1069ms
memory: 98836kb

Extra Test:

score: 0
Extra Test Passed