QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#524100#9155. 集合KingPowers100 ✓418ms67048kbC++141.8kb2024-08-19 10:26:192024-08-19 10:26:20

Judging History

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

  • [2024-08-19 10:26:20]
  • 评测
  • 测评结果:100
  • 用时:418ms
  • 内存:67048kb
  • [2024-08-19 10:26:19]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
#define deb(x) cerr << #x"=" << x << '\n';
using namespace std;
using ull = unsigned long long;
const int N = 6e5 + 5;
int n, m, q, cnt, a[N][3], b[N][3], pos[N];
ull w[N], ha[N], hb[N];
unordered_map<ull, int> mp;
mt19937_64 nrd(chrono::steady_clock::now().time_since_epoch().count());
void add(int x){
	if(mp[x] == -1) cnt--;
	else if(mp[x] == 0) cnt++;
	mp[x]++;
}
void del(int x){
	if(mp[x] == 1) cnt--;
	else if(mp[x] == 0) cnt++;
	mp[x]--;
}
void Add(int p){
	del(ha[a[p][0]]); del(ha[a[p][1]]); del(ha[a[p][2]]);
	ha[a[p][0]] += w[p]; ha[a[p][1]] += w[p]; ha[a[p][2]] += w[p];
	add(ha[a[p][0]]); add(ha[a[p][1]]); add(ha[a[p][2]]);

	add(hb[b[p][0]]); add(hb[b[p][1]]); add(hb[b[p][2]]);
	hb[b[p][0]] += w[p]; hb[b[p][1]] += w[p]; hb[b[p][2]] += w[p];
	del(hb[b[p][0]]); del(hb[b[p][1]]); del(hb[b[p][2]]);
}
void Del(int p){
	del(ha[a[p][0]]); del(ha[a[p][1]]); del(ha[a[p][2]]);
	ha[a[p][0]] -= w[p]; ha[a[p][1]] -= w[p]; ha[a[p][2]] -= w[p];
	add(ha[a[p][0]]); add(ha[a[p][1]]); add(ha[a[p][2]]);

	add(hb[b[p][0]]); add(hb[b[p][1]]); add(hb[b[p][2]]);
	hb[b[p][0]] -= w[p]; hb[b[p][1]] -= w[p]; hb[b[p][2]] -= w[p];
	del(hb[b[p][0]]); del(hb[b[p][1]]); del(hb[b[p][2]]);	
}
void Solve(){
	cin >> n >> m >> q;
	For(i, 1, n) cin >> a[i][0] >> a[i][1] >> a[i][2];
	For(i, 1, n) cin >> b[i][0] >> b[i][1] >> b[i][2];
	For(i, 1, n) w[i] = nrd();
	for(int i = 1, j = 0; i <= n; i++){
		while(j <= n && cnt == 0) Add(++j);
		Del(i); pos[i] = j - 1;
	}
	while(q--){
		int l, r; cin >> l >> r;
		cout << (pos[l] >= r ? "Yes" : "No") << '\n';
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while(T--) Solve();
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 16ms
memory: 11824kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 297ms
memory: 62564kb

Pretest #12:

score: 5
Accepted
time: 282ms
memory: 60172kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 100ms
memory: 12224kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 25ms
memory: 19212kb

Pretest #19:

score: 5
Accepted
time: 399ms
memory: 63044kb

Pretest #20:

score: 5
Accepted
time: 376ms
memory: 67048kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 16ms
memory: 12004kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 284ms
memory: 60572kb

Test #12:

score: 5
Accepted
time: 276ms
memory: 56276kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 3ms
memory: 12260kb

Test #15:

score: 5
Accepted
time: 99ms
memory: 12212kb

Test #16:

score: 5
Accepted
time: 103ms
memory: 12332kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 24ms
memory: 17104kb

Test #19:

score: 5
Accepted
time: 413ms
memory: 59972kb

Test #20:

score: 5
Accepted
time: 418ms
memory: 66820kb

Extra Test:

score: 0
Extra Test Passed