QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742462#7949. K-Lotteryyuto1115#Compile Error//Python34.1kb2024-11-13 16:39:162024-11-13 16:39:21

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 16:39:21]
  • 评测
  • [2024-11-13 16:39:16]
  • 提交

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;}

const int mod = 1000000007;

struct mint {
	ll x;
	mint(ll x=0) : x((x%mod+mod)%mod) {}

	mint &operator+=(mint a) { if((x += a.x) >= mod) x -= mod; return *this; }
	mint &operator-=(mint a) { if((x += mod-a.x) >= mod) x -= mod; return *this; }
	mint &operator*=(mint a) { (x *= a.x) %= mod; return *this; }

	mint operator+(mint a) { return mint(*this) += a; }
	mint operator-(mint a) { return mint(*this) -= a; }
	mint operator*(mint a) { return mint(*this) *= a; }

	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;

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));
	}
};

mt19937_64 engine(2111);
uniform_int_distribution<int> dist(0, mod-1);
const mint r = mint(dist(engine));

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int k,m,n;
	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);
	vm pw(n+1);
	pw[0] = 1;
	rep(i, n) pw[i+1] = pw[i] * r;
	auto add = [&](int i, ll x) {
		st.add(i+1, n, r);
		int cnt = st.calc(0,i).second;
		st.update(i, {pw[cnt] * x, 1});
	};
	mint r_iv = mint(r).inv();
	auto del = [&](int i) {
		st.add(i+1, n, r_iv);
		st.update(i, {0,0});
	};
	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 = st.calc(0, n).first;
			val -= sum * (i-k+1);
			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

  File "answer.code", line 9
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax