QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#742745 | #7949. K-Lottery | yuto1115# | TL | 0ms | 35088kb | C++20 | 5.4kb | 2024-11-13 17:13:26 | 2024-11-13 17:13:31 |
Judging History
answer
#include<bits/stdc++.h>
#define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i = ll(j)-1; i >= ll(k); i--)
#define rrep(i,k) rrep2(i,k,0)
#define eb emplace_back
#define SZ(a) ll(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX/4;
bool chmin(auto& a, auto b) {return a>b ? a=b, 1 : 0;}
bool chmax(auto& a, auto b) {return a<b ? a=b, 1 : 0;}
using u64 = uint64_t;
const u64 mod = inf;
random_device rnd;
const u64 r = ((u64)rnd() << 32 | rnd()) % mod;
u64 _add(u64 a, u64 b) {
a += b;
if(a >= mod) a -= mod;
return a;
}
u64 _mul(u64 a, u64 b) {
auto c = (__uint128_t)a * b;
return _add(c >> 61, c & mod);
}
struct mint {
u64 x;
mint(u64 x=0) : x((x%mod+mod)%mod) {}
mint &operator+=(mint a) { x = _add(x, a.x); return *this; }
mint &operator*=(mint a) { x = _mul(x, a.x); return *this; }
mint operator+(mint a) { return mint{_add(x, a.x)}; }
mint operator*(mint a) { return mint{_mul(x, a.x)}; }
mint pow(ll t) {
mint res(1), a(*this);
while(t) {
if(t&1) res *= a;
a *= a;
t >>= 1;
}
return res;
}
mint inv() { return pow(mod-2); }
};
using vm = vector<mint>;
using T = pair<mint, int>;
using S = mint;
int n;
const int MAX_SIZE = 1000005;
mint t[MAX_SIZE * 2], mul[MAX_SIZE * 2];
void eval(int v, int tl, int tr) {
t[v] = (t[v + 1] + t[v + (tr - tl & ~1)]) * mul[v];
}
void push(int v, int tl, int tr) {
if (mul[v].x != 1) {
if (tr - tl > 1) {
t[v + 1] *= mul[v];
t[v + (tr - tl & ~1)] *= mul[v];
mul[v + 1] *= mul[v];
mul[v + (tr - tl & ~1)] *= mul[v];
}
mul[v] = 1;
}
}
void update(int i, mint x, int v = 0, int tl = 0, int tr = n) {
push(v, tl, tr);
if (tr - tl == 1) t[v] = x;
else {
int m = tl + tr >> 1;
if (i < m) update(i, x, v + 1, tl, m);
else update(i, x, v + (tr - tl & ~1), m, tr);
eval(v, tl, tr);
}
}
void mul_interval(int l, int r, mint x, int v = 0, int tl = 0, int tr = n) {
if (tl >= r || tr <= l) return;
if (tl >= l && tr <= r) {
t[v] *= x;
mul[v] *= x;
} else {
int m = tl + tr >> 1;
mul_interval(l, r, x, v + 1, tl, m);
mul_interval(l, r, x, v + (tr - tl & ~1), m, tr);
eval(v, tl, tr);
}
}
struct lazy_segment_tree {
ll n;
ll LOG;
vector<T> node;
vector<S> lazy;
T vINF;
S lINF;
lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
vINF = vINF_;
lINF = lINF_;
n = 1;
LOG = 1;
while(n <= x.size()) n *= 2, LOG++;
node.resize(2*n, vINF);
lazy.resize(2*n, lINF);
rep(i,SZ(x)) node[i+n] = x[i];
rrep(i,n) node[i] = compare(node[i*2], node[i*2+1]);
}
T compare(T l, T r){
return {l.first + r.first, l.second + r.second};
}
T add1(T l, S r){
return {l.first * r, l.second};
}
S add2(S l, S r){
return l * r;
}
void eval(ll idx){
node[idx] = add1(node[idx], lazy[idx]);
if(idx < n){
lazy[idx*2] = add2(lazy[idx*2], lazy[idx]);
lazy[idx*2+1] = add2(lazy[idx*2+1], lazy[idx]);
}
lazy[idx] = lINF;
}
void update(ll idx, T val){
ll now = idx + n;
node[now] = val;
while(now > 0){
now >>= 1;
eval(now), eval(now*2), eval(now*2+1);
node[now] = compare(node[now*2], node[now*2+1]);
}
}
void add(ll l, ll r, S val, ll now = 1, ll left = 0, ll right = -1){
if(right == -1) right = n;
eval(now);
if(l <= left && right <= r){
lazy[now] = add2(lazy[now], val);
eval(now);
return;
}
if(r <= left || right <= l) return;
ll mid = (left+right)/2;
add(l, r, val, now*2, left, mid);
add(l, r, val, now*2+1, mid, right);
node[now] = compare(node[now*2], node[now*2+1]);
}
T calc(ll l, ll r, ll now = 1, ll left = 0, ll right = -1){
if(right == -1) right = n;
eval(now);
if(l <= left && right <= r) return node[now];
if(r <= left || right <= l) return vINF;
ll mid = (left+right)/2;
return compare(calc(l,r,now*2,left,mid), calc(l,r,now*2+1,mid,right));
}
};
struct BIT {
vl a;
BIT(ll n) : a(n+1) {}
void add(ll i, ll x) {
++i;
while(i < SZ(a)) {
a[i] += x;
i += i&-i;
}
}
ll sum(ll r) {
ll s = 0;
while(r) {
s += a[r];
r -= r&-r;
}
return s;
}
ll sum(ll l, ll r) {
return sum(r)-sum(l);
}
};
int main(){
cin.tie(0) -> sync_with_stdio(0);
int k,m;
cin >> k >> m >> n;
vvl tc(m, vl(k));
rep(i,m) rep(j,k) cin >> tc[i][j];
vl v(n);
rep(i, n) cin >> v[i];
vl cp = v;
sort(all(cp));
for(ll &i : v) i = lower_bound(all(cp), i) - cp.begin();
//lazy_segment_tree st(vector<T>(n, make_pair(0,0)), {0,0}, 1);
for (int i = 0; i < 2 * n; ++i) mul[i] = 1;
vm pw(n+1);
pw[0] = 1;
rep(i, n) pw[i+1] = pw[i] * r;
BIT bit(n);
auto add = [&](int i, ll x) {
mul_interval(i+1, n, r);
int cnt = bit.sum(0, i);
update(i, pw[cnt] * x);
bit.add(i, 1);
//printf("%lld\n", t[0].x);
};
mint r_iv = mint(r).inv();
auto del = [&](int i) {
mul_interval(i+1, n, r_iv);
update(i, 0);
bit.add(i, -1);
};
map<ll, int> mp;
rep(i, m) {
vl pos(k);
iota(all(pos), 0);
sort(all(pos), [&](int a, int b) { return tc[i][a] < tc[i][b]; });
mint val = 0;
rep(j, k) val += pw[j] * pos[j];
mp[val.x] = i;
}
mint sum = 0;
rep(i, k) sum += pw[i];
rep(i, n) {
if(i >= k) del(v[i-k]);
add(v[i], i);
if(i >= k-1) {
mint val = t[0];
mint rem = sum * (i-k+1);
val += mint(mod-rem.x);
if(mp.count(val.x)) {
int idx = mp[val.x];
rep(j, k) cout << tc[idx][j] << " \n"[j==k-1];
return 0;
}
}
}
cout << 0 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 35088kb
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: 0ms
memory: 34868kb
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: 0ms
memory: 34868kb
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...