QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488510 | #9155. 集合 | huangzirui | 100 ✓ | 1678ms | 426548kb | C++14 | 3.0kb | 2024-07-24 08:57:54 | 2024-07-24 08:57:55 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int maxn=600010;
int i,j,k,n,m,q;
int Ans[maxn];
int A[maxn][3],B[maxn][3];
int Num=0;
bool check(){
return Num==0;
}
unordered_map<ll,int>M;int cnt=0;
unordered_map<int,int>mS[2400010];
map<ll,int>id3,mp3;
multiset<int>S[2400010];int occ[maxn],tp[maxn];
bool isok(int id){
if(!occ[id])return true;
int num=tp[id];
for(auto x:S[id]){
if(-x==occ[id])--num;
else break;
if(num<=0)return true;
}
return false;
}
void EraseSet(int id,int id2){
Num-=!isok(id);occ[id]--;
for(int i=0;i<3;i++){
int w=B[id2][i];
S[id].erase(S[id].lower_bound(-mS[id][w]));
mS[id][w]--;if(mS[id][w])S[id].insert(-mS[id][w]);
}
Num+=!isok(id);
}
void InsertSet(int id,int id2){
Num-=!isok(id);occ[id]++;
for(int i=0;i<3;i++){
int w=B[id2][i];
if(mS[id][w])S[id].erase(S[id].lower_bound(-mS[id][w]));
mS[id][w]++;S[id].insert(-mS[id][w]);
}
Num+=!isok(id);
}
int getVal(int op,int id){
if(op==0)return 1ll*A[id][0]*m*m+1ll*A[id][1]*m+A[id][2];
if(op==1)return 1ll*B[id][0]*m*m+1ll*B[id][1]*m+B[id][2];
assert(0);
}
void Erase(int id){
for(int i=0;i<3;i++)
for(int j=i;j<3;j++){
ll sum=0;
for(int k=0;k<3;k++)
if(k==i || k==j)
sum=sum*(m+1)+A[id][k];
if(!M[sum])assert(0);
int tid=M[sum];
EraseSet(tid,id);
}
}
void Insert(int id){
for(int i=0;i<3;i++)
for(int j=i;j<3;j++){
ll sum=0;
for(int k=0;k<3;k++)
if(k==i || k==j)
sum=sum*(m+1)+A[id][k];
if(!M[sum]){
M[sum]=++cnt;
tp[cnt]=1+(i!=j);
}
int tid=M[sum];
InsertSet(tid,id);
}
}
void solve(){
M.clear();
map<ll,int>Mp;
for(int i=1;i<=n;i++){
ll val=getVal(0,i);
if(Mp[val]){
if(getVal(1,i)!=getVal(1,Mp[val]))
Ans[Mp[val]]=min(Ans[Mp[val]],i-1);
}Mp[val]=i;
}
for(int i=n-1;i>=1;i--)Ans[i]=min(Ans[i],Ans[i+1]);
int L=n;
for(int R=n;R>=1;R--){
Insert(R);
while(!check())Erase(L--);
Ans[R]=min(Ans[R],L);
}
while(L)Erase(L--);
}
void getAns(){
for(int i=1;i<=q;i++){
int l,r;
scanf("%d%d",&l,&r);
if(Ans[l]>=r)puts("Yes");
else puts("No");
}
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++)Ans[i]=n;
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++)
scanf("%d",&A[i][j]);
sort(A[i],A[i]+3);
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++)
scanf("%d",&B[i][j]);
sort(B[i],B[i]+3);
}
solve();
for(int i=1;i<=n;i++)
for(int j=0;j<3;j++)
swap(A[i][j],B[i][j]);
solve();
getAns();
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 39ms
memory: 249476kb
Pretest #2:
score: 5
Accepted
time: 31ms
memory: 249776kb
Pretest #3:
score: 5
Accepted
time: 39ms
memory: 249496kb
Pretest #4:
score: 5
Accepted
time: 42ms
memory: 249484kb
Pretest #5:
score: 5
Accepted
time: 33ms
memory: 249556kb
Pretest #6:
score: 5
Accepted
time: 28ms
memory: 249484kb
Pretest #7:
score: 5
Accepted
time: 35ms
memory: 249480kb
Pretest #8:
score: 5
Accepted
time: 28ms
memory: 249488kb
Pretest #9:
score: 5
Accepted
time: 54ms
memory: 249476kb
Pretest #10:
score: 5
Accepted
time: 51ms
memory: 249444kb
Pretest #11:
score: 5
Accepted
time: 882ms
memory: 253868kb
Pretest #12:
score: 5
Accepted
time: 913ms
memory: 253208kb
Pretest #13:
score: 5
Accepted
time: 44ms
memory: 249708kb
Pretest #14:
score: 5
Accepted
time: 48ms
memory: 251584kb
Pretest #15:
score: 5
Accepted
time: 153ms
memory: 249744kb
Pretest #16:
score: 5
Accepted
time: 166ms
memory: 251508kb
Pretest #17:
score: 5
Accepted
time: 158ms
memory: 256956kb
Pretest #18:
score: 5
Accepted
time: 152ms
memory: 264164kb
Pretest #19:
score: 5
Accepted
time: 1580ms
memory: 345292kb
Pretest #20:
score: 0
Wrong Answer
time: 1674ms
memory: 426548kb
Final Tests
Test #1:
score: 5
Accepted
time: 32ms
memory: 253636kb
Test #2:
score: 5
Accepted
time: 27ms
memory: 253564kb
Test #3:
score: 5
Accepted
time: 37ms
memory: 253576kb
Test #4:
score: 5
Accepted
time: 31ms
memory: 253536kb
Test #5:
score: 5
Accepted
time: 35ms
memory: 253524kb
Test #6:
score: 5
Accepted
time: 31ms
memory: 253592kb
Test #7:
score: 5
Accepted
time: 43ms
memory: 253556kb
Test #8:
score: 5
Accepted
time: 36ms
memory: 253640kb
Test #9:
score: 5
Accepted
time: 52ms
memory: 253504kb
Test #10:
score: 5
Accepted
time: 42ms
memory: 255616kb
Test #11:
score: 5
Accepted
time: 868ms
memory: 259704kb
Test #12:
score: 5
Accepted
time: 898ms
memory: 259748kb
Test #13:
score: 5
Accepted
time: 35ms
memory: 253812kb
Test #14:
score: 5
Accepted
time: 47ms
memory: 255500kb
Test #15:
score: 5
Accepted
time: 135ms
memory: 254120kb
Test #16:
score: 5
Accepted
time: 161ms
memory: 255164kb
Test #17:
score: 5
Accepted
time: 152ms
memory: 260104kb
Test #18:
score: 5
Accepted
time: 159ms
memory: 269264kb
Test #19:
score: 5
Accepted
time: 1553ms
memory: 336528kb
Test #20:
score: 5
Accepted
time: 1678ms
memory: 426036kb