QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#552330 | #9155. 集合 | Coder-Osman | 100 ✓ | 388ms | 60388kb | C++14 | 2.4kb | 2024-09-07 22:04:20 | 2024-09-07 22:04:21 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <random>
#include <cstdlib>
#define int long long
#define ull unsigned int
#define endl '\n'
#define lson 2*i
#define rson 2*i+1
#define debug(x) cerr << #x << " = " << x << "\n";
#define debug2(l,r) cerr << "[" #l "," #r "] = [" << l << "," << r << "]\n";
#define debug3(x,y,z) cerr << "{" #x "," #y "," #z "} = " << "{" << x << "," << y << "," << z << "}\n";
#define debugv(v) cerr << #v": size= " << v.size() << "\nelement: " ; for(auto p:v) cerr << p << " ";
using namespace std;
const int N = 2e5 + 55, M = 6e5 + 55, Q = 1e6 + 55, MOD = 1e9 + 7, INF = 1e18;
int n, m, q, a[N][4], b[N][4];
ull c[M], d[M], ar[N], br[N];
bool ans[Q];
bool func(int x) {
ull ha = 0, hb = 0;
for (int i = 1; i <= 3; i++) {
int t = a[x][i];
ha -= c[t];
c[t] ^= ar[x];
ha += c[t];
}
for (int i = 1; i <= 3; i++) {
int t = b[x][i];
hb -= d[t];
d[t] ^= ar[x];
hb += d[t];
}
if (ha == hb) return true;
for (int i = 1; i <= 3; i++)
c[a[x][i]] ^= ar[x];
for (int i = 1; i <= 3; i++)
d[b[x][i]] ^= ar[x];
return false;
}
void Delete(int x) {
for (int i = 1; i <= 3; i++)
c[a[x][i]] ^= ar[x];
for (int i = 1; i <= 3; i++)
d[b[x][i]] ^= ar[x];
}
mt19937_64 rd(random_device{}());
struct node {
int x, i;
};
vector<node> g[N];
signed main() {
cin.tie(0), ios_base::sync_with_stdio(false);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
ar[i] = rd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++)
cin >> a[i][j];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++)
cin >> b[i][j];
}
for (int i = 1, l, r; i <= q; i++) {
cin >> l >> r;
g[l].push_back({r, i});
}
for (int i = 1, j = 0; i <= n; i++) {
while (j < n) {
if (func(j + 1)) j++;
else break;
}
for (int k = 0; k < g[i].size(); k++) {
int x = g[i][k].x;
ans[g[i][k].i] = x <= j;
}
Delete(i);
}
for (int i = 1; i <= q; i++) {
if (ans[i]) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 16076kb
Pretest #2:
score: 5
Accepted
time: 3ms
memory: 15020kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 15560kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 16080kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 15812kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 16216kb
Pretest #7:
score: 5
Accepted
time: 3ms
memory: 16168kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 15048kb
Pretest #9:
score: 5
Accepted
time: 24ms
memory: 19420kb
Pretest #10:
score: 5
Accepted
time: 19ms
memory: 20320kb
Pretest #11:
score: 5
Accepted
time: 98ms
memory: 29320kb
Pretest #12:
score: 5
Accepted
time: 98ms
memory: 31412kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 15916kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 14832kb
Pretest #15:
score: 5
Accepted
time: 131ms
memory: 38608kb
Pretest #16:
score: 5
Accepted
time: 126ms
memory: 38820kb
Pretest #17:
score: 5
Accepted
time: 8ms
memory: 17388kb
Pretest #18:
score: 5
Accepted
time: 7ms
memory: 20996kb
Pretest #19:
score: 5
Accepted
time: 383ms
memory: 54156kb
Pretest #20:
score: 5
Accepted
time: 350ms
memory: 60024kb
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 15464kb
Test #2:
score: 5
Accepted
time: 3ms
memory: 16636kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 14976kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 17860kb
Test #5:
score: 5
Accepted
time: 3ms
memory: 15824kb
Test #6:
score: 5
Accepted
time: 3ms
memory: 16264kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 15360kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 16024kb
Test #9:
score: 5
Accepted
time: 22ms
memory: 20068kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 18792kb
Test #11:
score: 5
Accepted
time: 93ms
memory: 31632kb
Test #12:
score: 5
Accepted
time: 95ms
memory: 29328kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 16024kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 16256kb
Test #15:
score: 5
Accepted
time: 123ms
memory: 37204kb
Test #16:
score: 5
Accepted
time: 114ms
memory: 38436kb
Test #17:
score: 5
Accepted
time: 8ms
memory: 15520kb
Test #18:
score: 5
Accepted
time: 3ms
memory: 21176kb
Test #19:
score: 5
Accepted
time: 326ms
memory: 52024kb
Test #20:
score: 5
Accepted
time: 388ms
memory: 60388kb
Extra Test:
score: 0
Extra Test Passed