QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601778 | #9155. 集合 | Hunster# | 100 ✓ | 1239ms | 98836kb | C++20 | 5.7kb | 2024-09-30 13:01:19 | 2024-09-30 13:01:20 |
Judging History
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