QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#524100 | #9155. 集合 | KingPowers | 100 ✓ | 418ms | 67048kb | C++14 | 1.8kb | 2024-08-19 10:26:19 | 2024-08-19 10:26:20 |
Judging History
answer
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
#define deb(x) cerr << #x"=" << x << '\n';
using namespace std;
using ull = unsigned long long;
const int N = 6e5 + 5;
int n, m, q, cnt, a[N][3], b[N][3], pos[N];
ull w[N], ha[N], hb[N];
unordered_map<ull, int> mp;
mt19937_64 nrd(chrono::steady_clock::now().time_since_epoch().count());
void add(int x){
if(mp[x] == -1) cnt--;
else if(mp[x] == 0) cnt++;
mp[x]++;
}
void del(int x){
if(mp[x] == 1) cnt--;
else if(mp[x] == 0) cnt++;
mp[x]--;
}
void Add(int p){
del(ha[a[p][0]]); del(ha[a[p][1]]); del(ha[a[p][2]]);
ha[a[p][0]] += w[p]; ha[a[p][1]] += w[p]; ha[a[p][2]] += w[p];
add(ha[a[p][0]]); add(ha[a[p][1]]); add(ha[a[p][2]]);
add(hb[b[p][0]]); add(hb[b[p][1]]); add(hb[b[p][2]]);
hb[b[p][0]] += w[p]; hb[b[p][1]] += w[p]; hb[b[p][2]] += w[p];
del(hb[b[p][0]]); del(hb[b[p][1]]); del(hb[b[p][2]]);
}
void Del(int p){
del(ha[a[p][0]]); del(ha[a[p][1]]); del(ha[a[p][2]]);
ha[a[p][0]] -= w[p]; ha[a[p][1]] -= w[p]; ha[a[p][2]] -= w[p];
add(ha[a[p][0]]); add(ha[a[p][1]]); add(ha[a[p][2]]);
add(hb[b[p][0]]); add(hb[b[p][1]]); add(hb[b[p][2]]);
hb[b[p][0]] -= w[p]; hb[b[p][1]] -= w[p]; hb[b[p][2]] -= w[p];
del(hb[b[p][0]]); del(hb[b[p][1]]); del(hb[b[p][2]]);
}
void Solve(){
cin >> n >> m >> q;
For(i, 1, n) cin >> a[i][0] >> a[i][1] >> a[i][2];
For(i, 1, n) cin >> b[i][0] >> b[i][1] >> b[i][2];
For(i, 1, n) w[i] = nrd();
for(int i = 1, j = 0; i <= n; i++){
while(j <= n && cnt == 0) Add(++j);
Del(i); pos[i] = j - 1;
}
while(q--){
int l, r; cin >> l >> r;
cout << (pos[l] >= r ? "Yes" : "No") << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while(T--) Solve();
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 11832kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 11868kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 11868kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 11792kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 11868kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 11760kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 12028kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 11856kb
Pretest #9:
score: 5
Accepted
time: 16ms
memory: 11824kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 12064kb
Pretest #11:
score: 5
Accepted
time: 297ms
memory: 62564kb
Pretest #12:
score: 5
Accepted
time: 282ms
memory: 60172kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 12192kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 12292kb
Pretest #15:
score: 5
Accepted
time: 100ms
memory: 12224kb
Pretest #16:
score: 5
Accepted
time: 107ms
memory: 12336kb
Pretest #17:
score: 5
Accepted
time: 21ms
memory: 18136kb
Pretest #18:
score: 5
Accepted
time: 25ms
memory: 19212kb
Pretest #19:
score: 5
Accepted
time: 399ms
memory: 63044kb
Pretest #20:
score: 5
Accepted
time: 376ms
memory: 67048kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 11788kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 11956kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 11804kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 11996kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 11804kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 11824kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 11772kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 12068kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 12004kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 11844kb
Test #11:
score: 5
Accepted
time: 284ms
memory: 60572kb
Test #12:
score: 5
Accepted
time: 276ms
memory: 56276kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 12216kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 12260kb
Test #15:
score: 5
Accepted
time: 99ms
memory: 12212kb
Test #16:
score: 5
Accepted
time: 103ms
memory: 12332kb
Test #17:
score: 5
Accepted
time: 21ms
memory: 18184kb
Test #18:
score: 5
Accepted
time: 24ms
memory: 17104kb
Test #19:
score: 5
Accepted
time: 413ms
memory: 59972kb
Test #20:
score: 5
Accepted
time: 418ms
memory: 66820kb
Extra Test:
score: 0
Extra Test Passed