QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#491282 | #9155. 集合 | yushanen | 100 ✓ | 406ms | 58780kb | C++23 | 1.1kb | 2024-07-25 18:22:24 | 2024-07-25 18:22:24 |
Judging History
answer
#include <iostream>
#include <unordered_map>
#include <random>
using namespace std;
const int N = 2e5 + 10, M = 6e5 + 10;
int n, m, q, x, y, a[N][3], b[N][3], cur, req[N];
using ull = unsigned long long;
unordered_map<ull, int> mp;
random_device rd;
mt19937 mt(rd());
ull sg[N], pa[M], pb[M];
void upd(ull x, int v)
{
cur += !mp[x];
mp[x] += v;
cur -= !mp[x];
}
void acs(int x, int v)
{
for (int i = 0; i < 3; i++)
{
upd(pa[a[x][i]], -1);
pa[a[x][i]] += v * sg[x];
upd(pa[a[x][i]], 1);
upd(pb[b[x][i]], 1);
pb[b[x][i]] += v * sg[x];
upd(pb[b[x][i]], -1);
}
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 3; j++)
{
scanf("%d", a[i] + j);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 3; j++)
{
scanf("%d", b[i] + j);
}
}
for (int i = 1; i <= n; i++)
{
sg[i] = mt();
}
for (int i = 1, j = 1; i <= n; i++)
{
acs(i, 1);
while (cur)
acs(j, -1), j++;
req[i] = j;
}
for (int i = 1; i <= q; i++)
{
scanf("%d%d", &x, &y);
puts(req[y] <= x ? "Yes" : "No");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9832kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11864kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 9864kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9748kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9796kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 11916kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9828kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9824kb
Pretest #9:
score: 5
Accepted
time: 12ms
memory: 11872kb
Pretest #10:
score: 5
Accepted
time: 13ms
memory: 9828kb
Pretest #11:
score: 5
Accepted
time: 305ms
memory: 56344kb
Pretest #12:
score: 5
Accepted
time: 286ms
memory: 54460kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 10476kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10240kb
Pretest #15:
score: 5
Accepted
time: 100ms
memory: 10208kb
Pretest #16:
score: 5
Accepted
time: 107ms
memory: 10316kb
Pretest #17:
score: 5
Accepted
time: 20ms
memory: 14096kb
Pretest #18:
score: 5
Accepted
time: 25ms
memory: 15040kb
Pretest #19:
score: 5
Accepted
time: 406ms
memory: 54668kb
Pretest #20:
score: 5
Accepted
time: 393ms
memory: 58560kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 9820kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9752kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9756kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9864kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9860kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9760kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9824kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9892kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 10120kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 9896kb
Test #11:
score: 5
Accepted
time: 299ms
memory: 55036kb
Test #12:
score: 5
Accepted
time: 271ms
memory: 51260kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 10212kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 10184kb
Test #15:
score: 5
Accepted
time: 102ms
memory: 12260kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 12248kb
Test #17:
score: 5
Accepted
time: 18ms
memory: 16104kb
Test #18:
score: 5
Accepted
time: 20ms
memory: 15028kb
Test #19:
score: 5
Accepted
time: 361ms
memory: 54028kb
Test #20:
score: 5
Accepted
time: 395ms
memory: 58780kb
Extra Test:
score: 0
Extra Test Passed