QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#535542 | #9155. 集合 | lyx123886a123886# | 100 ✓ | 589ms | 58784kb | C++14 | 2.1kb | 2024-08-28 09:36:00 | 2024-08-28 09:36:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define LOCAL 0
#define open_file if(LOCAL) {freopen("set.in","r",stdin);freopen("set.out","w",stdout);}
// using LL=__int128;
using LL=unsigned long long;
mt19937_64 rd(304);
LL rng() {
LL hi=rd();if(hi<0) hi*=-1;hi<<=60;
LL lo=rd();if(lo<0) lo*=-1;
return hi^lo;
}
const int MAXN=2e5+50;
const int MAXM=6e5+50;
array<int,3> P[MAXN],Q[MAXN];LL hbs[MAXN];
LL hval0[MAXM],hval1[MAXM];
namespace c_wr {
// map<LL,int> ma;
unordered_map<LL,int> ma;
int count_wrong=0;
void upd(LL val,int type) {
// auto it=ma.find(val);
int curv=ma[val];
if(curv) count_wrong--;
if(curv+type) count_wrong++;
ma[val]+=type;
}
bool test() {
return !count_wrong;
}
};
int L,R;//[L,R)
namespace shift {
void r_shift() {
R++;
for(auto pos:P[R]) {
c_wr::upd(hval0[pos],-1);
hval0[pos]^=hbs[R];
c_wr::upd(hval0[pos],1);
}
for(auto pos:Q[R]) {
c_wr::upd(hval1[pos],1);
hval1[pos]^=hbs[R];
c_wr::upd(hval1[pos],-1);
}
}
void l_shift() {
for(auto pos:P[L]) {
c_wr::upd(hval0[pos],-1);
hval0[pos]^=hbs[L];
c_wr::upd(hval0[pos],1);
}
for(auto pos:Q[L]) {
c_wr::upd(hval1[pos],1);
hval1[pos]^=hbs[L];
c_wr::upd(hval1[pos],-1);
}
L++;
}
};
using shift::l_shift;
using shift::r_shift;
int rpos[MAXN];
void sol() {
int n,m,q;scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i) hbs[i]=rng();
for(int i=1;i<=n;++i) {
scanf("%d%d%d",&P[i][0],&P[i][1],&P[i][2]);
}
for(int i=1;i<=n;++i) {
scanf("%d%d%d",&Q[i][0],&Q[i][1],&Q[i][2]);
}
// R=0;
for(L=1,R=0;L<=n;l_shift()) {
while(R<=n&&c_wr::test()) r_shift();
rpos[L]=R-1;
}
for(;q;q--) {
int l,r;scanf("%d%d",&l,&r);
puts((r<=rpos[l])?"Yes":"No");
}
}
int main() {
open_file
sol() ;
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9872kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 12136kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 10104kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 11876kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 9868kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7828kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 10128kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 7804kb
Pretest #9:
score: 5
Accepted
time: 17ms
memory: 7824kb
Pretest #10:
score: 5
Accepted
time: 17ms
memory: 8048kb
Pretest #11:
score: 5
Accepted
time: 518ms
memory: 58748kb
Pretest #12:
score: 5
Accepted
time: 479ms
memory: 56448kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 10216kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10248kb
Pretest #15:
score: 5
Accepted
time: 107ms
memory: 8144kb
Pretest #16:
score: 5
Accepted
time: 107ms
memory: 10568kb
Pretest #17:
score: 5
Accepted
time: 25ms
memory: 14072kb
Pretest #18:
score: 5
Accepted
time: 20ms
memory: 15268kb
Pretest #19:
score: 5
Accepted
time: 589ms
memory: 57164kb
Pretest #20:
score: 5
Accepted
time: 589ms
memory: 58780kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 7812kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 7780kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 11904kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 8056kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9808kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 12148kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 12172kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 7792kb
Test #9:
score: 5
Accepted
time: 17ms
memory: 7824kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 11904kb
Test #11:
score: 5
Accepted
time: 469ms
memory: 56680kb
Test #12:
score: 5
Accepted
time: 395ms
memory: 54360kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 8052kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 12240kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 12532kb
Test #16:
score: 5
Accepted
time: 108ms
memory: 12328kb
Test #17:
score: 5
Accepted
time: 16ms
memory: 14116kb
Test #18:
score: 5
Accepted
time: 24ms
memory: 15060kb
Test #19:
score: 5
Accepted
time: 492ms
memory: 53716kb
Test #20:
score: 5
Accepted
time: 486ms
memory: 58784kb
Extra Test:
score: 0
Extra Test Passed