QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#506718#9155. 集合jijidawang100 ✓182ms20176kbC++202.0kb2024-08-05 20:53:482024-08-05 20:53:48

Judging History

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

  • [2024-08-05 20:53:48]
  • 评测
  • 测评结果:100
  • 用时:182ms
  • 内存:20176kb
  • [2024-08-05 20:53:48]
  • 提交

answer

 #include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define fileerr(x) freopen(x, "w", stderr);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd; 
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 2e5 + 233;
int n, m, q, a[N][3], b[N][3], ans[N];
mt19937_64 rnd(1);
ull xorshift(ull x){x ^= 1 << 13; x ^= x >> 7; x ^= x << 17; return x;}
ull hshA, hshB, val[N], valA[N * 3], valB[N * 3];
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i=1; i<=n; i++) scanf("%d%d%d", a[i], a[i]+1, a[i]+2);
	for (int i=1; i<=n; i++) scanf("%d%d%d", b[i], b[i]+1, b[i]+2);
	for (int i=1; i<=n; i++) val[i] = rnd();
	auto insert = [&](int p, int op)
	{
		for (int i=0; i<3; i++)
		{
			int x = a[p][i];
			hshA -= xorshift(valA[x]); valA[x] += val[p] * op; hshA += xorshift(valA[x]);
			x = b[p][i];
			hshB -= xorshift(valB[x]); valB[x] += val[p] * op; hshB += xorshift(valB[x]);
		}
	};
	for (int i=n, j=n; i>=1; i--)
	{
		insert(i, 1);
		while (hshA != hshB) insert(j--, -1);
		ans[i] = j;
	}
	int l, r;
	while (q--){scanf("%d%d", &l, &r); YN(ans[l] >= r);}
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 9908kb

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 14ms
memory: 9888kb

Pretest #10:

score: 5
Accepted
time: 21ms
memory: 9772kb

Pretest #11:

score: 5
Accepted
time: 58ms
memory: 11004kb

Pretest #12:

score: 5
Accepted
time: 69ms
memory: 10912kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 93ms
memory: 9964kb

Pretest #16:

score: 5
Accepted
time: 101ms
memory: 12024kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 4ms
memory: 12952kb

Pretest #19:

score: 5
Accepted
time: 174ms
memory: 12204kb

Pretest #20:

score: 5
Accepted
time: 182ms
memory: 20176kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

score: 5
Accepted
time: 1ms
memory: 9968kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 9816kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9904kb

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 21ms
memory: 9756kb

Test #10:

score: 5
Accepted
time: 17ms
memory: 11884kb

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 104ms
memory: 9896kb

Test #16:

score: 5
Accepted
time: 105ms
memory: 9924kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 8ms
memory: 10772kb

Test #19:

score: 5
Accepted
time: 169ms
memory: 11840kb

Test #20:

score: 5
Accepted
time: 171ms
memory: 20084kb

Extra Test:

score: 0
Extra Test Passed