QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492725#9155. 集合Felix72100 ✓272ms18468kbC++141.5kb2024-07-26 15:33:132024-07-26 15:33:15

Judging History

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

  • [2024-07-26 15:33:15]
  • 评测
  • 测评结果:100
  • 用时:272ms
  • 内存:18468kb
  • [2024-07-26 15:33:13]
  • 提交

answer

#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;

const int N = 200010;
int n, m, q, lim[N], a[N][3], b[N][3];

long long va, vb, na[N * 3], nb[N * 3];
inline void update(int pos, int opt)
{
	for(int i = 0; i <= 2; ++i)
	{
		va -= na[a[pos][i]] * na[a[pos][i]] * (long long)sqrtl(na[a[pos][i]]);
		na[a[pos][i]] += opt * 1ll * pos * pos * (long long)sqrtl(pos);
		va += na[a[pos][i]] * na[a[pos][i]] * (long long)sqrtl(na[a[pos][i]]);
		
		vb -= nb[b[pos][i]] * nb[b[pos][i]] * (long long)sqrtl(nb[b[pos][i]]);
		nb[b[pos][i]] += opt * 1ll * pos * pos * (long long)sqrtl(pos);
		vb += nb[b[pos][i]] * nb[b[pos][i]] * (long long)sqrtl(nb[b[pos][i]]);
	}
//	for(int i = 1; i <= 4; ++i) cerr << na[i] << " "; cerr << '\n';
//	for(int i = 1; i <= 4; ++i) cerr << nb[i] << " "; cerr << '\n';
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= 2; ++j)
			cin >> a[i][j];
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= 2; ++j)
			cin >> b[i][j];
	int r = 0;
	for(int l = 1; l <= n; ++l)
	{
		while(r < n)
		{
			++r; update(r, 1);
			if(va != vb)
			{
				update(r, -1); --r;
				break;
			}
		}
		lim[l] = r; update(l, -1);
	}
	for(int i = 1; i <= q; ++i)
	{
		int l, r; cin >> l >> r;
		if(r <= lim[l]) cout << "Yes" << '\n';
		else cout << "No" << '\n';
	}
	return 0;
}
/*
1100043
2 2 2 2 3 6 19 183
*/

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 136ms
memory: 10064kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 102ms
memory: 7740kb

Pretest #16:

score: 5
Accepted
time: 111ms
memory: 7916kb

Pretest #17:

score: 5
Accepted
time: 13ms
memory: 9768kb

Pretest #18:

score: 5
Accepted
time: 11ms
memory: 8772kb

Pretest #19:

score: 5
Accepted
time: 247ms
memory: 10700kb

Pretest #20:

score: 5
Accepted
time: 249ms
memory: 18468kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 18ms
memory: 7676kb

Test #10:

score: 5
Accepted
time: 18ms
memory: 9780kb

Test #11:

score: 5
Accepted
time: 129ms
memory: 9916kb

Test #12:

score: 5
Accepted
time: 137ms
memory: 10736kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 106ms
memory: 9728kb

Test #16:

score: 5
Accepted
time: 107ms
memory: 7848kb

Test #17:

score: 5
Accepted
time: 10ms
memory: 9768kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 233ms
memory: 10432kb

Test #20:

score: 5
Accepted
time: 272ms
memory: 18460kb

Extra Test:

score: 0
Extra Test Passed