QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#490152#9155. 集合Nangu100 ✓185ms20116kbC++141.4kb2024-07-25 12:07:412024-07-25 12:07:42

Judging History

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

  • [2024-07-25 12:07:42]
  • 评测
  • 测评结果:100
  • 用时:185ms
  • 内存:20116kb
  • [2024-07-25 12:07:41]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i, j, k) for(int i=(j); i<=(k); ++i)
#define R(i, j, k) for(int i=(j); i>=(k); --i)
#define G(v, i, u) for(int i=head[u], v=e[i].v; i; v=e[i=e[i].nxt].v)
#define de(x) cout<<#x<<" "<<x<<"  "
#define nd cout<<endl
#define P cout<<"Line:"<<" "<<__LINE__<<endl
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
using namespace std;
typedef unsigned long long ull;
const int N=2e5+7, M=6e5+7;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n, m, q, a[N][3], b[N][3], pos[N];
ull w[N], sa[M], sb[M], msk, s1, s2; 

ull shf(ull x){
	x^=msk, x^=x<<7, x^=x>>11, x^=x<<13;
	return x; 
}

void upd(int p, ull d){
	for(auto x:a[p]) s1-=shf(sa[x]), sa[x]+=d*w[p], s1+=shf(sa[x]); 
	for(auto x:b[p]) s2-=shf(sb[x]), sb[x]+=d*w[p], s2+=shf(sb[x]);
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n>>m>>q;
    F(i, 1, n) cin>>a[i][0]>>a[i][1]>>a[i][2];
    F(i, 1, n) cin>>b[i][0]>>b[i][1]>>b[i][2];
    F(i, 1, n) pos[i]=N;
    int T=1;
    while(T--){
    	msk=rng();
    	F(i, 1, n) w[i]=rng();
    	for(int i=1, j=1; i<=n; upd(i, -1), ++i){
			while(j<=n && s1==s2) upd(j, 1), ++j;
    		if(s1==s2) pos[i]=min(pos[i], j-1);
    		else pos[i]=min(pos[i], j-2);
		}
	}
//	F(i, 1, n) de(i), de(pos[i]), nd;
	while(q--){
		int a, b; cin>>a>>b;
		cout<<(pos[a]<b?"No\n":"Yes\n");
	}
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 20ms
memory: 11860kb

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 60ms
memory: 12432kb

Pretest #12:

score: 5
Accepted
time: 60ms
memory: 11448kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 6ms
memory: 9804kb

Pretest #18:

score: 5
Accepted
time: 5ms
memory: 10808kb

Pretest #19:

score: 5
Accepted
time: 159ms
memory: 10968kb

Pretest #20:

score: 5
Accepted
time: 178ms
memory: 20116kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 60ms
memory: 12240kb

Test #12:

score: 5
Accepted
time: 64ms
memory: 11496kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 5
Accepted
time: 6ms
memory: 9836kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 170ms
memory: 12504kb

Test #20:

score: 5
Accepted
time: 185ms
memory: 20064kb

Extra Test:

score: 0
Extra Test Passed