QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#509936#9155. 集合Rafi22#100 ✓518ms154392kbC++144.7kb2024-08-08 19:56:402024-08-08 19:56:42

Judging History

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

  • [2024-08-08 19:56:42]
  • 评测
  • 测评结果:100
  • 用时:518ms
  • 内存:154392kb
  • [2024-08-08 19:56:40]
  • 提交

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