QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490024 | #9155. 集合 | strcmp# | 100 ✓ | 228ms | 30596kb | C++14 | 1.4kb | 2024-07-25 10:27:30 | 2024-07-25 10:27:30 |
Judging History
answer
#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
#define gc getchar
#define pc putchar
#define rep(i, a, b) for(int i = a; i <= b; i++)
using namespace std;
using ld = double;
typedef unsigned long long int ll;
using pli = pair<ll, int>;
using ppi = pair<pli, int>;
using vec = vector<int>;
const ll inf = 1LL << 60;
constexpr int maxn = 6e5 + 10;
mt19937_64 rd(114514); int n, m, q, T = 5;
int a[2][maxn][4], R[maxn]; ll w[maxn], h[2][maxn], s[2], B;
inline ll trs(ll k) { return (k << 3 ^ k >> 7 ^ k << 17 ^ k ^ 0x3f5d2a) ^ B; }
inline void add(int p, int del) {
rep(o, 0, 1) {
rep(i, 1, 3) {
int u = a[o][p][i];
s[o] += trs(h[o][u]), h[o][u] += w[p] * del, s[o] -= trs(h[o][u]);
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &q); rep(i, 1, n) R[i] = n; rd.seed(time(NULL)); B = rd();
rep(o, 0, 1) rep(i, 1, n) rep(j, 1, 3) scanf("%d", &a[o][i][j]);
while (T--) {
rd.seed(rd()); s[0] = s[1] = 0;
rep(i, 1, n) w[i] = rd(); add(1, 1);
for (int l = 1, r = 1; l <= n; add(l++, -1)) {
while (r <= n && s[0] == s[1]) {
if (++r <= n) add(r, 1);
else break;
}
R[l] = min(R[l], r - 1);
}
}
while (q--) {
int l, r;
scanf("%d%d", &l, &r);
puts(r <= R[l] ? "Yes" : "No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 12084kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11948kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 12080kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 11944kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 11932kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 12080kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 12072kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 11872kb
Pretest #9:
score: 5
Accepted
time: 17ms
memory: 11888kb
Pretest #10:
score: 5
Accepted
time: 17ms
memory: 11948kb
Pretest #11:
score: 5
Accepted
time: 110ms
memory: 18220kb
Pretest #12:
score: 5
Accepted
time: 106ms
memory: 20184kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 12004kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 12164kb
Pretest #15:
score: 5
Accepted
time: 98ms
memory: 12084kb
Pretest #16:
score: 5
Accepted
time: 102ms
memory: 12096kb
Pretest #17:
score: 5
Accepted
time: 11ms
memory: 12084kb
Pretest #18:
score: 5
Accepted
time: 12ms
memory: 12996kb
Pretest #19:
score: 5
Accepted
time: 201ms
memory: 20204kb
Pretest #20:
score: 5
Accepted
time: 228ms
memory: 28636kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 11924kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 11932kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 12076kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 12056kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 12080kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 11932kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 11924kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 12004kb
Test #9:
score: 5
Accepted
time: 17ms
memory: 11888kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 11884kb
Test #11:
score: 5
Accepted
time: 106ms
memory: 20276kb
Test #12:
score: 5
Accepted
time: 109ms
memory: 18200kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 12080kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 14200kb
Test #15:
score: 5
Accepted
time: 92ms
memory: 11944kb
Test #16:
score: 5
Accepted
time: 89ms
memory: 12168kb
Test #17:
score: 5
Accepted
time: 5ms
memory: 12008kb
Test #18:
score: 5
Accepted
time: 12ms
memory: 12928kb
Test #19:
score: 5
Accepted
time: 205ms
memory: 18236kb
Test #20:
score: 5
Accepted
time: 220ms
memory: 30596kb
Extra Test:
score: 0
Extra Test Passed