QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491931 | #9155. 集合 | 5toubun_no_hanayome# | 100 ✓ | 191ms | 31316kb | C++14 | 4.0kb | 2024-07-26 01:27:21 | 2024-07-26 01:27:22 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;
const int N = 2e5 + 5, M = 6e5 + 5;
int a[N][3], b[N][3];
ull pos1[M][2], pos2[M][2];
ull w[N][2], s[2], t[2];
int f[N];
bool mt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
int n, m, q;
cin >> n >> m >> q;
rep(i, 1, n)
w[i][0] = rnd() % 998244353, w[i][1] = rnd() % 998244353;
rep(i, 1, n)
cin >> a[i][0] >> a[i][1] >> a[i][2];
rep(i, 1, n)
cin >> b[i][0] >> b[i][1] >> b[i][2];
for(int l = 1, r = 1;l <= n;++l) {
while(r <= n && s[0] == t[0] && s[1] == t[1]) {
rep(i, 0, 2) {
s[0] -= pos1[a[r][i]][0];
s[1] -= pos1[a[r][i]][1];
t[0] -= pos2[b[r][i]][0];
t[1] -= pos2[b[r][i]][1];
}
rep(i, 0, 2) {
pos1[a[r][i]][0] ^= w[r][0];
pos1[a[r][i]][1] ^= w[r][1];
pos2[b[r][i]][0] ^= w[r][0];
pos2[b[r][i]][1] ^= w[r][1];
}
rep(i, 0, 2) {
s[0] += pos1[a[r][i]][0];
s[1] += pos1[a[r][i]][1];
t[0] += pos2[b[r][i]][0];
t[1] += pos2[b[r][i]][1];
}
if(s[0] == t[0] && s[1] == t[1])
++r;
else {
rep(i, 0, 2) {
s[0] -= pos1[a[r][i]][0];
s[1] -= pos1[a[r][i]][1];
t[0] -= pos2[b[r][i]][0];
t[1] -= pos2[b[r][i]][1];
}
rep(i, 0, 2) {
pos1[a[r][i]][0] ^= w[r][0];
pos1[a[r][i]][1] ^= w[r][1];
pos2[b[r][i]][0] ^= w[r][0];
pos2[b[r][i]][1] ^= w[r][1];
}
rep(i, 0, 2) {
s[0] += pos1[a[r][i]][0];
s[1] += pos1[a[r][i]][1];
t[0] += pos2[b[r][i]][0];
t[1] += pos2[b[r][i]][1];
}
break;
}
}
f[l] = r;
rep(i, 0, 2) {
s[0] -= pos1[a[l][i]][0];
s[1] -= pos1[a[l][i]][1];
t[0] -= pos2[b[l][i]][0];
t[1] -= pos2[b[l][i]][1];
}
rep(i, 0, 2) {
pos1[a[l][i]][0] ^= w[l][0];
pos1[a[l][i]][1] ^= w[l][1];
pos2[b[l][i]][0] ^= w[l][0];
pos2[b[l][i]][1] ^= w[l][1];
}
rep(i, 0, 2) {
s[0] += pos1[a[l][i]][0];
s[1] += pos1[a[l][i]][1];
t[0] += pos2[b[l][i]][0];
t[1] += pos2[b[l][i]][1];
}
}
while(q--) {
int l, r;
cin >> l >> r;
if(r < f[l])
cout << "Yes\n";
else
cout << "No\n";
}
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 10028kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 8096kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 10092kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 8012kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 8072kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 10084kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 8072kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9900kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 8060kb
Pretest #10:
score: 5
Accepted
time: 12ms
memory: 10104kb
Pretest #11:
score: 5
Accepted
time: 69ms
memory: 14924kb
Pretest #12:
score: 5
Accepted
time: 63ms
memory: 14716kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 8000kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 8316kb
Pretest #15:
score: 5
Accepted
time: 100ms
memory: 8104kb
Pretest #16:
score: 5
Accepted
time: 97ms
memory: 10140kb
Pretest #17:
score: 5
Accepted
time: 0ms
memory: 10348kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 12092kb
Pretest #19:
score: 5
Accepted
time: 175ms
memory: 14744kb
Pretest #20:
score: 5
Accepted
time: 191ms
memory: 31316kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 7988kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 10120kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 7852kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10032kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 10112kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10044kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 8084kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 10036kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 10056kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 10056kb
Test #11:
score: 5
Accepted
time: 60ms
memory: 14924kb
Test #12:
score: 5
Accepted
time: 59ms
memory: 14904kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 8108kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 10204kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 8052kb
Test #16:
score: 5
Accepted
time: 104ms
memory: 8288kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 10164kb
Test #18:
score: 5
Accepted
time: 4ms
memory: 10324kb
Test #19:
score: 5
Accepted
time: 164ms
memory: 14744kb
Test #20:
score: 5
Accepted
time: 180ms
memory: 31224kb
Extra Test:
score: 0
Extra Test Passed