QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673990 | #7949. K-Lottery | AMATSUKAZE# | TL | 0ms | 3840kb | C++20 | 6.7kb | 2024-10-25 12:56:01 | 2024-10-25 12:56:02 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i,s,n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
using pll=pair<ll,ll>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vp=vector<pll>;
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 ull = unsigned long long;
const ull mod = (1ULL<<61)-1;
struct mm {
ull x;
mm (ull _x = 0) : x(_x) {}
mm &operator+=(mm a){
x += a.x;
if (x >= mod) x -= mod;
return *this;
}
mm &operator-=(mm a){
x += mod - a.x;
if (x >= mod) x -= mod;
return *this;
}
mm &operator*=(mm a){
x = (ull)((__uint128_t)(x) * a.x % mod);
return *this;
}
mm pow(ull n) const {
mm ret = *this, r = 1;
while (n != 0){
if (n & 1) ret *= r;
r *= r;
n >>= 1;
}
return ret;
}
mm &operator/=(mm a){
return *this *= a.pow(mod-2);
}
friend mm operator+(mm a, mm b){
return a += b;
}
friend mm operator-(mm a, mm b){
return a -= b;
}
friend mm operator*(mm a, mm b){
return a *= b;
}
friend mm operator/(mm a, mm b){
return a /= b;
}
friend bool operator<(mm a, mm b){
return a.x < b.x;
}
};
template<class S, auto op, auto e, class F, auto mapp, auto comp, auto id> struct lazyseg {
int n, sz, lg;
vector<S> d;
vector<F> lz;
void upd(int k) { d[k] = op(d[2*k], d[2*k+1]); }
void all_apply( int k, F f) {
d[k] = mapp(f, d[k]);
if (k < sz) lz[k] = comp(f, lz[k]);
}
void push(int k) {
all_apply(2*k, lz[k]);
all_apply(2*k+1, lz[k]);
lz[k] = id();
}
bool tail(int p, int i) { return ((p>>i)<<i)!=p; }
lazyseg(int _n = 0) : lazyseg(vector<S>(_n, e())) {}
lazyseg(vector<S> v): n(v.size()) {
sz = bit_ceil(uint32_t(n));
lg = countr_zero(uint32_t(sz));
d.assign(2*sz, e());
lz.assign(sz,id());
rep(i,0,n) d[sz+i] = v[i];
for(int i=sz-1; i>=1; i--) upd(i);
}
S prod(int l, int r){
if (l ==r ) return e();
l += sz, r += sz;
for (int i = lg; i>=1; i--) {
if (tail(l, i)) push(l >> i);
if (tail(r, i)) push(r >> i);
}
S sml = e(), smr = e();
while(l < r){
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml ,smr);
}
void set(int p, S x) {
p += sz;
for (int i=lg; i>=1; i--) push(p >> i);
d[p] = x;
for (int i=1; i<=lg; i++) upd(p>>i);
}
S get(int p) {
p += sz;
for (int i=lg; i>=1; i--) push(p >> i);
return d[p];
}
void apply(int l, int r, F f) {
if (l == r) return;
l += sz, r += sz;
for (int i=lg; i>=1; i--) {
if (tail(l,i)) push(l >> i);
if (tail(r,i)) push((r-1)>>i);
}
int l2 = l, r2 = r;
while( l < r) {
if(l & 1) all_apply(l++, f);
if(r & 1) all_apply(--r, f);
l >>= 1; r >>= 1;
}
l = l2, r = r2;
for (int i=1; i<=lg; i++){
if (tail(l,i)) upd(l >> i);
if (tail(r,i)) upd((r-1) >> i);
}
}
int max_right(int l, auto g) {
if (l == n) return n;
l += sz;
for (int i=lg; i>=1; i--) push(l >> i);
S sm = e();
do {
while(l % 2 == 0) l >>= 1;
if (!g(op(sm,d[l]))) {
while(l < sz) {
push(l);
l <<= 1;
if(g(op(sm,d[l]))) {sm = op(sm,d[l++]);}
}
return l - sz;
}
sm = op(sm, d[l++]);
} while ((l&-l)!=l);
return n;
}
int min_left(int r, auto g) {
if (r == 0) return 0;
r += sz;
for (int i=lg; i>=1; i--) push((r-1)>>i);
S sm = e();
do {
r--;
while(r > 1 && (r %2)) r >>= 1;
if (!g(op(d[r],sm))){
while(r<sz){
push(r);
r=(2*r+1);
if (g(op(d[r],sm))){
sm=op(d[r--],sm);
}
}
return r+1-sz;
}
sm=op(d[r],sm);
}while((r&-r)!=r);
return 0;
}
};
using mint = mm;
using vm=vector<mint>;
const int L=3;
using T=array<mint,L>;
struct S{
T a;
ll s;
};
random_device rnd;
mt19937_64 mt(rnd());
T base,inv;
array<vm,L> pows,sums;
S op(S x, S y){
rep(i,0,L) x.a[i]+=y.a[i]*pows[i][x.s];
x.s+=y.s;
return x;
}
S e(){
return S{T(),0};
}
S mapping(ll f, S x){
rep(i,0,L) x.a[i]+=sums[i][x.s]*f;
return x;
}
ll composition(ll f, ll g){
return f + g;
}
ll ident(){
return 0;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
ll k,m,n;
cin>>k>>m>>n;
rep(i,0,L) base[i]=mt()%mod;
// base[0]=2;
rep(i,0,L){
pows[i]=vm(k);
sums[i]=vm(k+1);
pows[i][0]=1;
rep(j,1,k) pows[i][j]=pows[i][j-1]*base[i];
rep(j,0,k) sums[i][j+1]+=sums[i][j]+pows[i][j];
}
vvl ps(m,vl(k));
vvl qs(m,vl(k));
map<T,ll> mp;
rep(i,0,m)rep(j,0,k) cin>>ps[i][j];
rep(i,0,m)rep(j,0,k) qs[i][ps[i][j]-1]=k-j;
rep(i,0,m){
T ar;
rep(l,0,L){
mint x=0;
rrep(j,0,k) x=x*base[l]+qs[i][j];
ar[l]=x;
}
mp[ar]=i;
// rep(j,0,L) cout<<ar[j].x<<' ';cout<<endl;
}
vl a(n);
rep(i,0,n) cin>>a[i];
{
map<ll,ll> tp;
vl b=a;
sort(all(b));
rep(i,0,n) tp[b[i]]=i;
rep(i,0,n) a[i]=tp[a[i]];
}
lazyseg<S,op,e,ll,mapping,composition,ident> st(n);
rep(i,0,n){
ll x=a[i];
T ar;
rep(l,0,L) ar[l]=1;
st.apply(0,n,1);
st.set(x,S{ar,1});
T h=st.prod(0,n).a;
// rep(j,0,L) cout<<h[j].x<<' ';cout<<endl;
if(mp.find(h)!=mp.end()){
vl rs=ps[mp[h]];
rep(j,0,k) cout<<rs[j]<<" \n"[j==n-1];
return 0;
}
if(i>=k-1){
ll y=a[i-k+1];
st.set(y,e());
}
}
cout<<0<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
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: 3576kb
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: 3496kb
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...