QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688255 | #7949. K-Lottery | tamthegod | TL | 7ms | 18216kb | C++14 | 5.1kb | 2024-10-30 01:38:18 | 2024-10-30 01:38:18 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int k, m, n;
int a[maxN];
int Hash[maxN];
vector<vector<int>> vc;
int id[maxN];
const int base = 2345723;
int pw[maxN];
map<int, int> mp;
int inv[maxN];
int poww(int k, int n)
{
int res = 1;
while(n)
{
if(n & 1) res = (res * k) % mod;
k = (k * k) % mod;
n /= 2;
}
return res;
}
void ReadInput()
{
pw[0] = 1;
for(int i=1; i<maxN; i++)
pw[i] = (pw[i - 1] * base) % mod;
cin >> k >> m >> n;
vc.resize(m + 5, vector<int> (k + 5));
for(int i=1; i<=m; i++)
for(int j=1; j<=k; j++)
cin >> vc[i][j];
for(int i=1; i<=m; i++)
{
for(int j=1; j<=k; j++)
id[vc[i][j]] = j;
for(int j=1; j<=k; j++)
Hash[i] = (Hash[i] + id[j] * pw[j - 1] % mod) % mod;
mp[Hash[i]] = i;
}
vector<int> val;
for(int i=1; i<=n; i++)
{
cin >> a[i];
val.pb(a[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for(int i=1; i<=n; i++)
a[i] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
for(int i=0; i<=n; i++)
inv[i] = poww(pw[i], mod - 2);
}
int mark;
struct LazySegtree
{
vector<pair<int, int>> st;
vector<int> lazy;
void init(int n)
{
st.resize(4 * n + 5, {});
lazy.resize(4 * n + 5, 0);
}
void refind(int id)
{
st[id].fi = (st[id * 2].fi + st[id * 2 + 1].fi) % mod;
st[id].se = st[id * 2].se + st[id * 2 + 1].se;
}
void down(int id)
{
int t = lazy[id];
if(!t) return;
if(t > 0)
{
st[id * 2].fi = (st[id * 2].fi * pw[t]) % mod;
st[id * 2 + 1].fi = (st[id * 2 + 1].fi * pw[t]) % mod;
}
else if(t < 0)
{
st[id * 2].fi = (st[id * 2].fi * inv[-t]) % mod;
st[id * 2 + 1].fi = (st[id * 2 + 1].fi * inv[-t]) % mod;
}
lazy[id * 2] += t;
lazy[id * 2 + 1] += t;
lazy[id] = 0;
}
void update(int id, int l, int r, int pos, int val1, int val2)
{
if(l > pos || r < pos) return;
if(l == r && l == pos)
{
st[id] = {val1, val2};
return;
}
down(id);
int mid = (l + r) / 2;
update(id * 2, l, mid, pos, val1, val2);
update(id * 2 + 1, mid + 1, r, pos, val1, val2);
refind(id);
}
void range_upd(int id, int l, int r, int u, int v, int val)
{
if(l > v || r < u) return;
if(l >= u && r <= v)
{
if(val > 0) st[id].fi = (st[id].fi * pw[val]) % mod;
else st[id].fi = (st[id].fi * inv[-val]) % mod;
lazy[id] += val;
return;
}
int mid = (l + r) / 2;
down(id);
range_upd(id * 2, l, mid, u, v, val);
range_upd(id * 2 + 1, mid + 1, r, u, v, val);
refind(id);
}
pair<int, int> get(int id, int l, int r, int u, int v)
{
if(l > v || r < u || l > r) return {0, 0};
if(l >= u && r <= v) return st[id];
int mid = (l + r) / 2;
down(id);
auto L = get(id * 2, l, mid, u, v), R = get(id * 2 + 1, mid + 1, r, u, v);
return {(L.fi + R.fi) % mod, L.se + R.se};
}
};
void Solve()
{
//for(int i=1; i<=n; i++)
// cout << a[i] << " ";return;
LazySegtree tree;
tree.init(n);
int cur = 0;
int tmp = 0;
for(int i=0; i<k; i++)
{
tmp = (tmp + pw[i]) % mod;
}
for(int i=1; i<=n; i++)
{
if(i > k)
{
tree.update(1, 1, n, a[i - k], 0, 0);
tree.range_upd(1, 1, n, a[i - k] + 1, n, -1);
}
auto val = tree.get(1, 1, n, 1, a[i] - 1);
tree.range_upd(1, 1, n, a[i] + 1, n, 1);
tree.update(1, 1, n, a[i], (i * pw[val.se]) % mod, 1);
int res = tree.st[1].fi;
if(i >= k)
{
res -= cur;
if(res < 0) res += mod;
if(mp[res])
{
int i = mp[res];
for(int j=1; j<=k; j++)
cout << vc[i][j] << " ";
return;
}
cur += tmp;
cur %= mod;
}
}
cout << 0;
}
#define taskname "sol"
int32_t main()
{
if (fopen(taskname ".inp", "r"))
{
freopen(taskname ".inp", "r", stdin);
//freopen(taskname ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
//cin >> T;
for(int itest=1; itest<=T; itest++)
{
ReadInput();
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 18216kb
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: 3ms
memory: 16012kb
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: 7ms
memory: 18056kb
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...
output:
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 5037 38 5038 39 50...