QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492725 | #9155. 集合 | Felix72 | 100 ✓ | 272ms | 18468kb | C++14 | 1.5kb | 2024-07-26 15:33:13 | 2024-07-26 15:33:15 |
Judging History
answer
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 200010;
int n, m, q, lim[N], a[N][3], b[N][3];
long long va, vb, na[N * 3], nb[N * 3];
inline void update(int pos, int opt)
{
for(int i = 0; i <= 2; ++i)
{
va -= na[a[pos][i]] * na[a[pos][i]] * (long long)sqrtl(na[a[pos][i]]);
na[a[pos][i]] += opt * 1ll * pos * pos * (long long)sqrtl(pos);
va += na[a[pos][i]] * na[a[pos][i]] * (long long)sqrtl(na[a[pos][i]]);
vb -= nb[b[pos][i]] * nb[b[pos][i]] * (long long)sqrtl(nb[b[pos][i]]);
nb[b[pos][i]] += opt * 1ll * pos * pos * (long long)sqrtl(pos);
vb += nb[b[pos][i]] * nb[b[pos][i]] * (long long)sqrtl(nb[b[pos][i]]);
}
// for(int i = 1; i <= 4; ++i) cerr << na[i] << " "; cerr << '\n';
// for(int i = 1; i <= 4; ++i) cerr << nb[i] << " "; cerr << '\n';
}
int main()
{
// freopen("text.in", "r", stdin);
// freopen("prog.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= 2; ++j)
cin >> a[i][j];
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= 2; ++j)
cin >> b[i][j];
int r = 0;
for(int l = 1; l <= n; ++l)
{
while(r < n)
{
++r; update(r, 1);
if(va != vb)
{
update(r, -1); --r;
break;
}
}
lim[l] = r; update(l, -1);
}
for(int i = 1; i <= q; ++i)
{
int l, r; cin >> l >> r;
if(r <= lim[l]) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
return 0;
}
/*
1100043
2 2 2 2 3 6 19 183
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 7808kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9764kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 7728kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 7736kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 7744kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7712kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9792kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 7728kb
Pretest #9:
score: 5
Accepted
time: 21ms
memory: 9768kb
Pretest #10:
score: 5
Accepted
time: 18ms
memory: 9776kb
Pretest #11:
score: 5
Accepted
time: 136ms
memory: 10064kb
Pretest #12:
score: 5
Accepted
time: 136ms
memory: 9904kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 7744kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 7760kb
Pretest #15:
score: 5
Accepted
time: 102ms
memory: 7740kb
Pretest #16:
score: 5
Accepted
time: 111ms
memory: 7916kb
Pretest #17:
score: 5
Accepted
time: 13ms
memory: 9768kb
Pretest #18:
score: 5
Accepted
time: 11ms
memory: 8772kb
Pretest #19:
score: 5
Accepted
time: 247ms
memory: 10700kb
Pretest #20:
score: 5
Accepted
time: 249ms
memory: 18468kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 7684kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9676kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 7632kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 9824kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 7728kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 7756kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 7756kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 7816kb
Test #9:
score: 5
Accepted
time: 18ms
memory: 7676kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 9780kb
Test #11:
score: 5
Accepted
time: 129ms
memory: 9916kb
Test #12:
score: 5
Accepted
time: 137ms
memory: 10736kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 7648kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 7824kb
Test #15:
score: 5
Accepted
time: 106ms
memory: 9728kb
Test #16:
score: 5
Accepted
time: 107ms
memory: 7848kb
Test #17:
score: 5
Accepted
time: 10ms
memory: 9768kb
Test #18:
score: 5
Accepted
time: 14ms
memory: 8740kb
Test #19:
score: 5
Accepted
time: 233ms
memory: 10432kb
Test #20:
score: 5
Accepted
time: 272ms
memory: 18460kb
Extra Test:
score: 0
Extra Test Passed