QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#489644 | #9155. 集合 | Fracture-Dream | 100 ✓ | 675ms | 115972kb | C++14 | 2.8kb | 2024-07-24 22:12:19 | 2024-07-24 22:12:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 6e5 + 5;
int n , m , q , rnk[MAXN] , suma[MAXN] , sumb[MAXN] , posr[MAXN] , all;
int a[MAXN][3] , b[MAXN][3];
unordered_map<int , int> mpA , mpB;
mt19937 rd(time(0));
uniform_int_distribution<int>val(-1e9 , 1e9);
int f(int id) {return rnk[id] * id;}
void adda(int pos , int id , int tp) {
if (suma[pos]) {
all -= abs(mpA[suma[pos]] - mpB[suma[pos]]);
mpA[suma[pos]] --;
all += abs(mpA[suma[pos]] - mpB[suma[pos]]);
}
suma[pos] += f(id) * tp;
if (suma[pos]) {
all -= abs(mpA[suma[pos]] - mpB[suma[pos]]);
mpA[suma[pos]] ++;
all += abs(mpA[suma[pos]] - mpB[suma[pos]]);
}
}
void addb(int pos , int id , int tp) {
if (sumb[pos]) {
all -= abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
mpB[sumb[pos]] --;
all += abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
}
sumb[pos] += f(id) * tp;
if (sumb[pos]) {
all -= abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
mpB[sumb[pos]] ++;
all += abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr) , cout.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1 ; i <= n ; i ++) rnk[i] = val(rd) * val(rd);
for (int i = 1 ; i <= n ; i ++) cin >> a[i][0] >> a[i][1] >> a[i][2];
for (int i = 1 ; i <= n ; i ++) cin >> b[i][0] >> b[i][1] >> b[i][2];
int l = 1 , r = 1;
for (int i = 0 ; i < 3 ; i ++) adda(a[1][i] , 1 , 1);
for (int i = 0 ; i < 3 ; i ++) addb(b[1][i] , 1 , 1);
while(l <= n) {
if (!all) {
posr[l] = r;
if (r == n) {
for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);
l ++;
} else {
r ++;
for (int i = 0 ; i < 3 ; i ++) adda(a[r][i] , r , 1);
for (int i = 0 ; i < 3 ; i ++) addb(b[r][i] , r , 1);
}
} else {
if (l == r) {
for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);
l ++ , r ++;
for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , 1);
for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , 1);
} else {
for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);
l ++;
}
}
}
for (int i = 1 ; i <= n ; i ++) posr[i] = max(posr[i - 1] , posr[i]);
while(q --) {
int l , r;
cin >> l >> r;
if (posr[l] >= r) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 10056kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9864kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9800kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9792kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 9832kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9792kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9856kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9904kb
Pretest #9:
score: 5
Accepted
time: 21ms
memory: 10160kb
Pretest #10:
score: 5
Accepted
time: 14ms
memory: 10132kb
Pretest #11:
score: 5
Accepted
time: 566ms
memory: 115972kb
Pretest #12:
score: 5
Accepted
time: 538ms
memory: 109720kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 10692kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 12912kb
Pretest #15:
score: 5
Accepted
time: 108ms
memory: 10676kb
Pretest #16:
score: 5
Accepted
time: 113ms
memory: 10728kb
Pretest #17:
score: 5
Accepted
time: 35ms
memory: 19316kb
Pretest #18:
score: 5
Accepted
time: 37ms
memory: 23352kb
Pretest #19:
score: 5
Accepted
time: 675ms
memory: 110256kb
Pretest #20:
score: 5
Accepted
time: 661ms
memory: 105692kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9844kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 10096kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 10076kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9868kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9792kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 9800kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 9912kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 9912kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 10148kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 9908kb
Test #11:
score: 5
Accepted
time: 516ms
memory: 106392kb
Test #12:
score: 5
Accepted
time: 532ms
memory: 107380kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 10912kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 12948kb
Test #15:
score: 5
Accepted
time: 112ms
memory: 10640kb
Test #16:
score: 5
Accepted
time: 105ms
memory: 10628kb
Test #17:
score: 5
Accepted
time: 36ms
memory: 19300kb
Test #18:
score: 5
Accepted
time: 32ms
memory: 19652kb
Test #19:
score: 5
Accepted
time: 632ms
memory: 110764kb
Test #20:
score: 5
Accepted
time: 659ms
memory: 112784kb
Extra Test:
score: 0
Extra Test Passed