QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544082#9155. 集合jay_jayjay#100 ✓900ms135272kbC++174.1kb2024-09-02 03:51:022024-09-02 03:51:02

Judging History

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

  • [2024-09-02 03:51:02]
  • 评测
  • 测评结果:100
  • 用时:900ms
  • 内存:135272kb
  • [2024-09-02 03:51:02]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(),(x).end()


#define ll long long
#define ull unsigned ll


//#define dprintf printf
#define dprintf(args...) 59
mt19937_64 rng(42);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

 //chinese io here we come
#define BUFSZ (1<<21)
char ib[BUFSZ], *ip=ib+BUFSZ;
char ob[BUFSZ], *op=ob;
#define gc() (ip==ib+BUFSZ?(fread(ip=ib,BUFSZ,1,stdin),*ip++):*ip++)

int read() {
        char c; while((c=gc())<'0');
        int x=c-'0';
        while((c=gc())>='0')x=x*10+(c-'0');
        return x;
}
struct { template<class T> operator T() { T x; cin>>x; return x; } } in;
//struct { operator int() { return read(); } } in;

void write(const string&& s) {
        for(auto x:s)*op++=x;
}
void flush() {
        fwrite(ob,op-ob,1,stdout);
        op=ob;
}


#define N int(2e5)
#define M int(6e5)
int a[N][3]; int b[N][3];
ull eh[N]; ull ha[M], hb[M];

int ans[N];
//map<int,int> ga, gb;
gp_hash_table<int,int> ga,gb;

int bad=0;
int n,m,qq;

int main()
{
        n=in, m=in, qq=in;

        for(int i=0;i<n;i++) for(int j=0;j<3;j++)a[i][j]=in,a[i][j]--;
        for(int i=0;i<n;i++) for(int j=0;j<3;j++)b[i][j]=in,b[i][j]--;
        for(int i=0;i<n;i++) {
                //eh[i]=1ull<<i;
                eh[i] = rng();
        }

        auto alter = [&](int j) -> void {
                dprintf("alter %d\n",j);
                //set<int> cs;
                vector<int> cs;
                for(auto k : a[j]) {
                        cs.push_back(ha[k]);
                        cs.push_back(ha[k]^eh[j]);
                }
                for(auto k : b[j]) {
                        cs.push_back(hb[k]);
                        cs.push_back(hb[k]^eh[j]);
                }
                sort(all(cs));
                cs.erase(unique(all(cs)),cs.end());
                for(auto x : cs) {
                        if(ga[x] != gb[x]) bad--;
                }
                for(auto x : a[j]) {
                        ga[ha[x]]--;
                        if(ga[ha[x]]==0)ga.erase(ha[x]);
                        ha[x] ^= eh[j];
                        ga[ha[x]]++;
                }
                for(auto x : b[j]) {
                        gb[hb[x]]--;
                        if(ga[hb[x]]==0)ga.erase(hb[x]);
                        hb[x] ^= eh[j];
                        gb[hb[x]]++;
                }
                for(auto x : cs) {
                        if(ga[x] != gb[x]) bad++;
                }
        };

        for(int i=0;i<m;i++) dprintf("%d ", ha[i]%100);
        dprintf("\n");
        for(int i=0;i<m;i++) dprintf("%d ", hb[i]%100);
        dprintf("\n");
        int j=-1;
        for(int i=0;i<n;i++) {
                while(j<n && !bad) {
                        dprintf("(%d, %d)\n",i,j);
                        for(int i=0;i<m;i++) dprintf("%d ", ha[i]%100);
                        dprintf("\n");
                        for(int i=0;i<m;i++) dprintf("%d ", hb[i]%100);
                        dprintf("\n");
                        dprintf("\t\t%d bad\n",bad);
                        j++;
                        if(j<n)alter(j);
                }
                for(int i=0;i<m;i++) dprintf("%d ", ha[i]%100);
                dprintf("\n");
                for(int i=0;i<m;i++) dprintf("%d ", hb[i]%100);
                dprintf("\n");
                dprintf("\t\t%d bad\n",bad);
                ans[i] = j;
                dprintf("ans %d = %d\n", i, j);
                alter(i);
        }

        while(qq--) {
                int l=in, r=in;
                l--; r--;

                if(r<ans[l]) {
                        write("Yes\n");
                        //puts("Yes");
                }
                else {
                        write("No\n");
                        //puts("No");
                }
                if(qq%10000==0) flush();
        }
        return flush(),0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 11820kb

Pretest #2:

score: 5
Accepted
time: 1ms
memory: 9660kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 11720kb

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 12020kb

Pretest #5:

score: 5
Accepted
time: 2ms
memory: 11824kb

Pretest #6:

score: 5
Accepted
time: 2ms
memory: 11832kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 11768kb

Pretest #8:

score: 5
Accepted
time: 2ms
memory: 11772kb

Pretest #9:

score: 5
Accepted
time: 49ms
memory: 12040kb

Pretest #10:

score: 5
Accepted
time: 42ms
memory: 9840kb

Pretest #11:

score: 5
Accepted
time: 568ms
memory: 135272kb

Pretest #12:

score: 5
Accepted
time: 512ms
memory: 73596kb

Pretest #13:

score: 5
Accepted
time: 7ms
memory: 12496kb

Pretest #14:

score: 5
Accepted
time: 7ms
memory: 12204kb

Pretest #15:

score: 5
Accepted
time: 276ms
memory: 10360kb

Pretest #16:

score: 5
Accepted
time: 280ms
memory: 12516kb

Pretest #17:

score: 5
Accepted
time: 44ms
memory: 19200kb

Pretest #18:

score: 5
Accepted
time: 51ms
memory: 20156kb

Pretest #19:

score: 5
Accepted
time: 883ms
memory: 73652kb

Pretest #20:

score: 5
Accepted
time: 895ms
memory: 82364kb

Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 11712kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 11824kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 11776kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 11776kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 11716kb

Test #6:

score: 5
Accepted
time: 0ms
memory: 11944kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 11888kb

Test #8:

score: 5
Accepted
time: 0ms
memory: 11880kb

Test #9:

score: 5
Accepted
time: 49ms
memory: 11912kb

Test #10:

score: 5
Accepted
time: 42ms
memory: 11828kb

Test #11:

score: 5
Accepted
time: 517ms
memory: 73392kb

Test #12:

score: 5
Accepted
time: 520ms
memory: 75768kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 12340kb

Test #14:

score: 5
Accepted
time: 8ms
memory: 12632kb

Test #15:

score: 5
Accepted
time: 278ms
memory: 10312kb

Test #16:

score: 5
Accepted
time: 287ms
memory: 12588kb

Test #17:

score: 5
Accepted
time: 45ms
memory: 19264kb

Test #18:

score: 5
Accepted
time: 54ms
memory: 20156kb

Test #19:

score: 5
Accepted
time: 845ms
memory: 73584kb

Test #20:

score: 5
Accepted
time: 900ms
memory: 81376kb

Extra Test:

score: 0
Extra Test Passed