QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544082 | #9155. 集合 | jay_jayjay# | 100 ✓ | 900ms | 135272kb | C++17 | 4.1kb | 2024-09-02 03:51:02 | 2024-09-02 03:51:02 |
Judging History
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