QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#509936 | #9155. 集合 | Rafi22# | 100 ✓ | 518ms | 154392kb | C++14 | 4.7kb | 2024-08-08 19:56:40 | 2024-08-08 19:56:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;
const int N=200007,M=600007;
vector<int>A[N],B[N];
int R[N];
int id[M];
vector<int>sA[10*N];
vector<int>sB[10*N];
int it;
int used[M];
bool is[M];
bool isA[M];
bool isB[M];
bool takenA[M];
bool takenB[M];
struct mem
{
int x,it1;
vector<pair<int,int>>C;
};
vector<mem>S;
int Rollback()
{
int X=S.back().x;
it-=S.back().it1;
for(auto i:B[X]) used[i]--;
for(auto [i,x]:S.back().C) id[i]=x;
S.pop_back();
return X;
}
void add(int x)
{
mem xd;
xd.x=x;
xd.it1=0;
debug(x);
vector<int>P;
for(auto i:A[x])
{
debug(i,id[i],is[id[i]]);
if(!is[id[i]]&&id[i]!=0) P.pb(id[i]);
is[id[i]]=1;
isA[i]=1;
}
for(auto i:B[x]) isB[i]=1;
for(auto p:P)
{
debug(p);
vector<int>A1,B1,A2,B2;
for(auto i:sA[p])
{
if(isA[i]) A1.pb(i);
else A2.pb(i);
}
for(auto i:sB[p])
{
if(isB[i]) B1.pb(i);
else B2.pb(i);
}
it++,xd.it1++;
sA[it]=A1,sB[it]=B1;
for(auto i:sA[it])
{
xd.C.pb({i,id[i]});
id[i]=it;
}
for(auto i:A1) takenA[i]=1;
for(auto i:B1) takenB[i]=1;
if(sz(A2)>0)
{
it++,xd.it1++;
sA[it]=A2,sB[it]=B2;
for(auto i:sA[it])
{
xd.C.pb({i,id[i]});
id[i]=it;
}
}
}
vector<int>A1,B1;
for(auto i:A[x]) if(!takenA[i]) A1.pb(i);
for(auto i:B[x]) if(!takenB[i]) B1.pb(i);
if(sz(A1)>0)
{
it++,xd.it1++;
sA[it]=A1,sB[it]=B1;
for(auto i:sA[it])
{
xd.C.pb({i,id[i]});
id[i]=it;
}
}
for(auto i:A[x])
{
isA[i]=0;
takenA[i]=0;
}
for(auto i:B[x])
{
isB[i]=0;
takenB[i]=0;
used[i]++;
}
for(auto i:P) is[i]=0;
S.pb(xd);
}
bool check(int x)
{
bool OK=1;
vector<int>P;
for(auto i:A[x])
{
if(!is[id[i]]&&id[i]!=0) P.pb(id[i]);
is[id[i]]=1;
isA[i]=1;
}
for(auto i:B[x]) isB[i]=1;
for(auto p:P)
{
debug(p);
vector<int>A1,B1,A2,B2;
for(auto i:sA[p])
{
if(isA[i]) A1.pb(i);
else A2.pb(i);
}
for(auto i:sB[p])
{
if(isB[i]) B1.pb(i);
else B2.pb(i);
}
if(sz(A1)!=sz(B1)) OK=0;
for(auto i:A1) takenA[i]=1;
for(auto i:B1) takenB[i]=1;
}
vector<int>A1,B1;
for(auto i:A[x]) if(!takenA[i]) A1.pb(i);
for(auto i:B[x]) if(!takenB[i]) B1.pb(i);
if(sz(A1)>0)
{
for(auto i:B1) if(used[i]) OK=0;
}
for(auto i:A[x])
{
isA[i]=0;
takenA[i]=0;
}
for(auto i:B[x])
{
isB[i]=0;
takenB[i]=0;
}
for(auto i:P) is[i]=0;
if(OK) add(x);
return OK;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
FOR(i,1,n)
{
A[i].resize(3);
FOR(j,0,2) cin>>A[i][j];
}
FOR(i,1,n)
{
B[i].resize(3);
FOR(j,0,2) cin>>B[i][j];
}
int j=0;
FOR(i,1,n)
{
while(j<n&&check(j+1)) j++;
R[i]=j;
debug(j);
vector<int>V;
int ile=0;
while(true)
{
int x=Rollback();
if(x==i) break;
ile++;
V.pb(x);
}
while(sz(S)>0&&ile>0)
{
V.pb(Rollback());
ile--;
}
sort(all(V),greater<int>());
for(auto x:V) add(x);
}
while(q--)
{
int l,r;
cin>>l>>r;
if(R[l]>=r) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 15ms
memory: 108092kb
Pretest #2:
score: 5
Accepted
time: 11ms
memory: 109920kb
Pretest #3:
score: 5
Accepted
time: 12ms
memory: 110292kb
Pretest #4:
score: 5
Accepted
time: 16ms
memory: 108388kb
Pretest #5:
score: 5
Accepted
time: 11ms
memory: 111212kb
Pretest #6:
score: 5
Accepted
time: 8ms
memory: 111180kb
Pretest #7:
score: 5
Accepted
time: 7ms
memory: 108520kb
Pretest #8:
score: 5
Accepted
time: 8ms
memory: 110328kb
Pretest #9:
score: 5
Accepted
time: 29ms
memory: 108112kb
Pretest #10:
score: 5
Accepted
time: 35ms
memory: 111848kb
Pretest #11:
score: 5
Accepted
time: 299ms
memory: 147924kb
Pretest #12:
score: 5
Accepted
time: 287ms
memory: 145376kb
Pretest #13:
score: 5
Accepted
time: 12ms
memory: 112308kb
Pretest #14:
score: 5
Accepted
time: 16ms
memory: 110408kb
Pretest #15:
score: 5
Accepted
time: 118ms
memory: 108660kb
Pretest #16:
score: 5
Accepted
time: 122ms
memory: 110468kb
Pretest #17:
score: 5
Accepted
time: 38ms
memory: 114284kb
Pretest #18:
score: 5
Accepted
time: 37ms
memory: 114004kb
Pretest #19:
score: 5
Accepted
time: 437ms
memory: 149448kb
Pretest #20:
score: 5
Accepted
time: 518ms
memory: 153296kb
Final Tests
Test #1:
score: 5
Accepted
time: 12ms
memory: 107968kb
Test #2:
score: 5
Accepted
time: 13ms
memory: 111064kb
Test #3:
score: 5
Accepted
time: 7ms
memory: 111396kb
Test #4:
score: 5
Accepted
time: 12ms
memory: 109900kb
Test #5:
score: 5
Accepted
time: 16ms
memory: 110364kb
Test #6:
score: 5
Accepted
time: 14ms
memory: 111212kb
Test #7:
score: 5
Accepted
time: 7ms
memory: 113076kb
Test #8:
score: 5
Accepted
time: 7ms
memory: 111280kb
Test #9:
score: 5
Accepted
time: 32ms
memory: 113356kb
Test #10:
score: 5
Accepted
time: 30ms
memory: 110544kb
Test #11:
score: 5
Accepted
time: 272ms
memory: 145856kb
Test #12:
score: 5
Accepted
time: 270ms
memory: 145984kb
Test #13:
score: 5
Accepted
time: 20ms
memory: 110984kb
Test #14:
score: 5
Accepted
time: 11ms
memory: 108564kb
Test #15:
score: 5
Accepted
time: 123ms
memory: 111584kb
Test #16:
score: 5
Accepted
time: 124ms
memory: 111728kb
Test #17:
score: 5
Accepted
time: 42ms
memory: 114212kb
Test #18:
score: 5
Accepted
time: 47ms
memory: 114688kb
Test #19:
score: 5
Accepted
time: 451ms
memory: 150356kb
Test #20:
score: 5
Accepted
time: 436ms
memory: 154392kb
Extra Test:
score: 0
Extra Test Passed