QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497382 | #9155. 集合 | tosivan | 100 ✓ | 1317ms | 188924kb | C++14 | 4.0kb | 2024-07-29 03:47:54 | 2024-07-29 03:47:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[200005][3],b[200005][3];
ll lasta[600005],lastb[600005];
ll theleft[600005];
bool exista[600005],existb[600005],exist[600005];
map<ll,vector<pair<ll,ll> > >mp,mp2;
map<ll,vector<pair<ll,ll> > >rng[600005];
void reconstruct(ll x, ll it, ll cur){
// cout<<"hi\n";
vector<pair<ll,ll> >bruh;
for(auto& u: mp[x]){
if(u.first!=it)bruh.push_back(u);
else{
rng[x][u.first].push_back({u.second,cur-1});
// cout<<x<<" "<<u.first<<' '<<u.second<<' '<<cur-1<<'\n';
}
}
mp[x].swap(bruh);
}
void reconstruct2(ll x, ll it){
// cout<<"hi\n";
vector<pair<ll,ll> >bruh;
for(auto& u: mp2[x]){
if(u.first!=it)bruh.push_back(u);
}
mp2[x].swap(bruh);
}
void kill(ll id){
for(int i=0;i<3;i++){
exista[a[id][i]]=1,existb[b[id][i]]=1;
}
for(int i=0;i<3;i++){
vector<ll>bb;
for(auto& [u,lef]: mp[a[id][i]]){
if(!existb[u])bb.push_back(u);
}
for(auto& u: bb){
reconstruct(a[id][i],u,id),reconstruct2(u,a[id][i]);
}
}
for(int i=0;i<3;i++){
vector<ll>bb;
for(auto& [u,lef]: mp2[b[id][i]]){
if(!exista[u])bb.push_back(u);
}
for(auto& u: bb){
reconstruct(u,b[id][i],id),reconstruct2(b[id][i],u);
}
}
for(int i=0;i<3;i++){
exista[a[id][i]]=0,existb[b[id][i]]=0;
}
for(int i=0;i<3;i++){
for(auto& [u,lef]: mp[a[id][i]])exist[u]=1;
for(int j=0;j<3;j++){
if(!exist[b[id][j]]){mp[a[id][i]].push_back({b[id][j],max(lasta[a[id][i]],lastb[b[id][j]])+1});}
}
for(auto& [u,lef]: mp[a[id][i]])exist[u]=0;
}
for(int i=0;i<3;i++){
for(auto& [u,lef]: mp2[b[id][i]])exist[u]=1;
for(int j=0;j<3;j++){
if(!exist[a[id][j]]){mp2[b[id][i]].push_back({a[id][j],max(lasta[a[id][j]],lastb[b[id][i]])+1});}
}
for(auto& [u,lef]: mp2[b[id][i]])exist[u]=0;
}
}
bool test(ll id1, ll id2, ll lef, ll righ){
if(rng[id1][id2].size()==0)return 0;
// cout<<"nigger\n";
if(rng[id1][id2][0].first>lef)return 0;
ll l=0,r=rng[id1][id2].size()-1;
while(l<r){
ll mid=(l+r+1)>>1;
if(rng[id1][id2][mid].first<=lef){
l=mid;
}
else{
r=mid-1;
}
}
if(rng[id1][id2][l].second>=righ)return 1;
return 0;
}
bool ok(vector<ll>v, ll l, ll r){
for(int i=0;i<3;i++){
if(!test(v[i],b[r][i],l,r))return 0;
}
return 1;
}
bool tameshi(ll l, ll r){
vector<ll>v;
for(int i=0;i<3;i++)v.push_back(a[r][i]);
sort(v.begin(),v.end());
if(ok(v,l,r))return 1;
while(next_permutation(v.begin(),v.end())){
if(ok(v,l,r))return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for(int i=0;i<2;i++){
for(int j=0;j<600005;j++){
exist[j]=0;
}
}
ll n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
lasta[i]=0,lastb[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++){
cin>>b[i][j];
}
}
for(int i=1;i<=n;i++){
kill(i);
for(int j=0;j<3;j++){
lasta[a[i][j]]=i,lastb[b[i][j]]=i;
}
}
for(int i=1;i<=m;i++){
for(auto& [u,lef]: mp[i]){
rng[i][u].push_back({lef,n});
// cout<<i<<" "<<u<<" "<<lef<<" "<<n<<" "<<'\n';
}
}
ll leftest[n+5];
leftest[1]=1;
ll ptr=1;
for(int i=2;i<=n;i++){
while(!tameshi(ptr,i))ptr++;
leftest[i]=ptr;
}
while(q--){
ll l,r;
cin>>l>>r;
if(leftest[r]>l)cout<<"No\n";
else cout<<"Yes\n";
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 42872kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 41944kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 41868kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 42564kb
Pretest #5:
score: 5
Accepted
time: 3ms
memory: 41356kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 41684kb
Pretest #7:
score: 5
Accepted
time: 3ms
memory: 42036kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 42096kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 41352kb
Pretest #10:
score: 5
Accepted
time: 24ms
memory: 41892kb
Pretest #11:
score: 5
Accepted
time: 461ms
memory: 59392kb
Pretest #12:
score: 5
Accepted
time: 517ms
memory: 64428kb
Pretest #13:
score: 5
Accepted
time: 7ms
memory: 41876kb
Pretest #14:
score: 5
Accepted
time: 14ms
memory: 43644kb
Pretest #15:
score: 5
Accepted
time: 112ms
memory: 42592kb
Pretest #16:
score: 5
Accepted
time: 107ms
memory: 42520kb
Pretest #17:
score: 5
Accepted
time: 79ms
memory: 46760kb
Pretest #18:
score: 5
Accepted
time: 89ms
memory: 59096kb
Pretest #19:
score: 5
Accepted
time: 1073ms
memory: 89688kb
Pretest #20:
score: 5
Accepted
time: 1292ms
memory: 188248kb
Final Tests
Test #1:
score: 5
Accepted
time: 4ms
memory: 42324kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 41780kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 42096kb
Test #4:
score: 5
Accepted
time: 4ms
memory: 42156kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 41412kb
Test #6:
score: 5
Accepted
time: 3ms
memory: 41460kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 42172kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 41640kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 43164kb
Test #10:
score: 5
Accepted
time: 24ms
memory: 42072kb
Test #11:
score: 5
Accepted
time: 451ms
memory: 59596kb
Test #12:
score: 5
Accepted
time: 542ms
memory: 64008kb
Test #13:
score: 5
Accepted
time: 11ms
memory: 41632kb
Test #14:
score: 5
Accepted
time: 8ms
memory: 44060kb
Test #15:
score: 5
Accepted
time: 106ms
memory: 42200kb
Test #16:
score: 5
Accepted
time: 110ms
memory: 43288kb
Test #17:
score: 5
Accepted
time: 76ms
memory: 48732kb
Test #18:
score: 5
Accepted
time: 88ms
memory: 58080kb
Test #19:
score: 5
Accepted
time: 1065ms
memory: 86564kb
Test #20:
score: 5
Accepted
time: 1317ms
memory: 188924kb
Extra Test:
score: 0
Extra Test Passed