QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672639 | #7949. K-Lottery | ucup-team3519# | TL | 810ms | 316320kb | C++17 | 5.6kb | 2024-10-24 17:54:51 | 2024-10-24 17:54:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef __int128_t LLL;
#define V vector
#define pb push_back
typedef unsigned long long ULL;
typedef long long LL;
#define lb lower_bound
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
const int N = 2e6 + 10;
const LL mod = 444445555566666677;
const LL base = 23333;
LL MOD(LL x) {
if(x >= mod) x -= mod;
if(x < 0) x += mod;
return x;
}
LL mul(LL a, LL b) {
return (__int128_t)a * b % mod;
}
LL qpow(LL x, LL k) {
LL ans = 1;
while(k) {
if(k & 1) ans = mul(ans, x);
k /= 2;
x = mul(x, x);
}
return ans;
}
struct Node {
LL sum_val, sum_pbs, mul_pbs, add_val, fine;
Node() {
sum_pbs = 0, sum_val = 0, mul_pbs = 1, add_val = 0, fine = 1;
}
} seg[N << 2];
void pull_up(int node) {
seg[node].sum_val = MOD(seg[node << 1].sum_val * seg[node << 1].fine + seg[node << 1 | 1].sum_val * seg[node << 1 | 1].fine);
seg[node].sum_pbs = MOD(seg[node << 1].sum_pbs * seg[node << 1].fine + seg[node << 1 | 1].sum_pbs * seg[node << 1 | 1].fine);
}
void apply(int node, LL mul_pbs, LL add_val) {
seg[node].sum_pbs = mul(seg[node].sum_pbs, mul_pbs);
seg[node].sum_val = mul(seg[node].sum_val, mul_pbs);
seg[node].sum_val = MOD(seg[node].sum_val + mul(seg[node].sum_pbs, add_val));
seg[node].mul_pbs = mul(mul_pbs, seg[node].mul_pbs);
seg[node].add_val = MOD(add_val + seg[node].add_val);
}
void push_down(int node) {
if (seg[node].mul_pbs != 1 || seg[node].add_val) {
LL &tag = seg[node].mul_pbs;
LL &add = seg[node].add_val;
apply(node << 1, tag, add);
apply(node << 1 | 1, tag, add);
tag = 1;
add = 0;
}
}
void flip_fine(int node, int L, int R, int pos) {
if (L == R) {
seg[node].fine ^= 1;
return;
}
push_down(node);
int mid = (L + R) / 2;
if (pos <= mid) flip_fine(node << 1, L, mid, pos);
else flip_fine(node << 1 | 1, mid + 1, R, pos);
pull_up(node);
}
void modify(int node, int L, int R, int pos, LL val) {
if (L == R) {
seg[node].sum_val = mul(val, seg[node].sum_pbs);
return;
}
push_down(node);
int mid = (L + R) / 2;
if (pos <= mid) modify(node << 1, L, mid, pos, val);
else modify(node << 1 | 1, mid + 1, R, pos, val);
pull_up(node);
}
void modify_pbs(int node, int L, int R, int pos, LL pbs) {
if (L == R) {
seg[node].sum_pbs = pbs;
return;
}
push_down(node);
int mid = (L + R) / 2;
if (pos <= mid) modify_pbs(node << 1, L, mid, pos, pbs);
else modify_pbs(node << 1 | 1, mid + 1, R, pos, pbs);
pull_up(node);
}
void seg_show(int node, int L, int R, int pos) {
if (L == R) {
cout << "sum _val _pbs : " << seg[node].sum_val << " " << seg[node].sum_pbs << endl;
cout << "tag _val _pbs : " << seg[node].add_val << " " << seg[node].mul_pbs << endl;
cout << "fine : " << seg[node].fine << endl;
return;
}
push_down(node);
int mid = (L + R) / 2;
if (pos <= mid) seg_show(node << 1, L, mid, pos);
else seg_show(node << 1 | 1, mid + 1, R, pos);
pull_up(node);
}
void range_apply(int node, int L, int R, int l, int r, LL tag, LL add) {
if (l <= L && R <= r) {
apply(node, tag, add);
return;
}
push_down(node);
int mid = (L + R) / 2;
if (l <= mid) range_apply(node << 1, L, mid, l, r, tag, add);
if (r > mid) range_apply(node << 1 | 1, mid + 1, R, l, r, tag, add);
pull_up(node);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int k, m; cin >> k >> m;
int n; cin >> n;
LL inv_base = qpow(base, mod - 2);
V<LL> hs(m + 1);
V<V<int>> tab(m + 1);
for(int i = 1; i <= m; i++) {
V<int> a(k + 1);
for(int j = 1; j <= k; j++) cin >> a[j];
tab[i] = a;
V<int> pos(k + 1);
for(int j = 1; j <= k; j++) pos[a[j]] = j;
LL cur = 0;
for(int j = 1; j <= k; j++) {
cur = MOD(mul(cur, base) + pos[j]);
}
hs[i] = cur;
}
map<LL, int> mp;
for(int i = 1; i <= m; i++) mp[hs[i]] = i;
V<int> sheet(n + 1);
for(int i = 1; i <= n; i++) cin >> sheet[i];
V<int> ord(n + 1);
iota(all1(ord), 1);
sort(all1(ord), [&](int x, int y) {
return sheet[x] < sheet[y];
});
for(int i = 1; i <= n; i++) sheet[ord[i]] = i;
int tot = 2e6;
for(int i = 1; i <= tot; i++) flip_fine(1, 1, tot, i);
for(int i = 1; i <= tot; i++) modify_pbs(1, 1, tot, i, 1);
auto show = [&](int n) -> void {
for(int i = 1; i <= n; i++) seg_show(1, 1, tot, i);
};
// show(10);
auto add = [&](int x) -> void {
if(x != 1) range_apply(1, 1, tot, 1, x - 1, base, 0);
// cout << "add :" << x << endl;
modify(1, 1, tot, x, k);
flip_fine(1, 1, tot, x);
};
auto del = [&](int x) -> void {
if(x != 1) range_apply(1, 1, tot, 1, x - 1, inv_base, 0);
flip_fine(1, 1, tot, x);
};
auto get = [&]() -> LL {
return seg[1].sum_val;
};
for(int i = 1; i <= n; i++) {
if(i - k >= 1) del(sheet[i - k]);
add(sheet[i]);
// show(10);
if(mp.count(get())) {
int id = mp[get()];
for(int i = 1; i <= k; i++) cout << tab[id][i] << " ";
cout << endl;
return 0;
}
// cout << get() << endl;
range_apply(1, 1, tot, 1, tot, 1, -1);
}
cout << 0 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 810ms
memory: 316032kb
input:
3 2 10 1 2 3 1 3 2 20 35 10 7 99 53 72 33 88 16
output:
1 3 2
result:
ok single line: '1 3 2 '
Test #2:
score: 0
Accepted
time: 778ms
memory: 316320kb
input:
4 5 10 1 2 3 4 1 2 4 3 3 4 1 2 4 1 2 3 4 2 3 1 19 31 9 1 89 48 63 30 78 12
output:
4 2 3 1
result:
ok single line: '4 2 3 1 '
Test #3:
score: 0
Accepted
time: 780ms
memory: 316112kb
input:
3 3 7 1 3 2 2 3 1 2 1 3 11 22 33 44 55 66 77
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Time Limit Exceeded
input:
10000 10 1000000 1 5001 2 5002 3 5003 4 5004 5 5005 6 5006 7 5007 8 5008 9 5009 10 5010 11 5011 12 5012 13 5013 14 5014 15 5015 16 5016 17 5017 18 5018 19 5019 20 5020 21 5021 22 5022 23 5023 24 5024 25 5025 26 5026 27 5027 28 5028 29 5029 30 5030 31 5031 32 5032 33 5033 34 5034 35 5035 36 5036 37 5...