QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742818#7949. K-Lotteryyuto1115#Compile Error//C++205.4kb2024-11-13 17:24:022024-11-13 17:24:02

Judging History

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

  • [2024-11-13 17:24:02]
  • 评测
  • [2024-11-13 17:24:02]
  • 提交

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

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

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

詳細信息

answer.code:110:16: error: ‘T’ was not declared in this scope
  110 |         vector<T> node;
      |                ^
answer.code:110:17: error: template argument 1 is invalid
  110 |         vector<T> node;
      |                 ^
answer.code:110:17: error: template argument 2 is invalid
answer.code:111:16: error: ‘S’ was not declared in this scope
  111 |         vector<S> lazy;
      |                ^
answer.code:111:17: error: template argument 1 is invalid
  111 |         vector<S> lazy;
      |                 ^
answer.code:111:17: error: template argument 2 is invalid
answer.code:112:9: error: ‘T’ does not name a type
  112 |         T vINF;
      |         ^
answer.code:113:9: error: ‘S’ does not name a type
  113 |         S lINF;
      |         ^
answer.code:114:40: error: ‘T’ was not declared in this scope
  114 |         lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
      |                                        ^
answer.code:114:41: error: template argument 1 is invalid
  114 |         lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
      |                                         ^
answer.code:114:41: error: template argument 2 is invalid
answer.code:114:47: error: ‘T’ has not been declared
  114 |         lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
      |                                               ^
answer.code:114:56: error: ‘S’ has not been declared
  114 |         lazy_segment_tree(const vector<T> &x, T vINF_, S lINF_){
      |                                                        ^
answer.code:125:9: error: ‘T’ does not name a type
  125 |         T compare(T l, T r){
      |         ^
answer.code:128:9: error: ‘T’ does not name a type
  128 |         T add1(T l, S r){
      |         ^
answer.code:131:9: error: ‘S’ does not name a type
  131 |         S add2(S l, S r){
      |         ^
answer.code:144:29: error: ‘T’ has not been declared
  144 |         void update(ll idx, T val){
      |                             ^
answer.code:154:30: error: ‘S’ has not been declared
  154 |         void add(ll l, ll r, S val, ll now = 1, ll left = 0, ll right = -1){
      |                              ^
answer.code:170:9: error: ‘T’ does not name a type
  170 |         T calc(ll l, ll r, ll now = 1, ll left = 0, ll right = -1){
      |         ^
answer.code: In constructor ‘lazy_segment_tree::lazy_segment_tree(const int&, int, int)’:
answer.code:115:17: error: ‘vINF’ was not declared in this scope; did you mean ‘vINF_’?
  115 |                 vINF = vINF_;
      |                 ^~~~
      |                 vINF_
answer.code:116:17: error: ‘lINF’ was not declared in this scope; did you mean ‘lINF_’?
  116 |                 lINF = lINF_;
      |                 ^~~~
      |                 lINF_
answer.code:119:30: error: request for member ‘size’ in ‘x’, which is of non-class type ‘const int’
  119 |                 while(n <= x.size()) n *= 2, LOG++;
      |                              ^~~~
answer.code:120:22: error: request for member ‘resize’ in ‘((lazy_segment_tree*)this)->lazy_segment_tree::node’, which is of non-class type ‘int’
  120 |                 node.resize(2*n, vINF);
      |                      ^~~~~~
answer.code:121:22: error: request for member ‘resize’ in ‘((lazy_segment_tree*)this)->lazy_segment_tree::lazy’, which is of non-class type ‘int’
  121 |                 lazy.resize(2*n, lINF);
      |                      ^~~~~~
answer.code:7:20: error: request for member ‘size’ in ‘x’, which is of non-class type ‘const int’
    7 | #define SZ(a) ll(a.size())
      |                    ^~~~
answer.code:2:46: note: in definition of macro ‘rep2’
    2 | #define rep2(i,j,k) for(ll i = ll(j); i < ll(k); i++)
      |                                              ^
answer.code:122:17: note: in expansion of macro ‘rep’
  122 |                 rep(i,SZ(x)) node[i+n] = x[i];
      |                 ^~~
answer.code:122:23: note: in expansion of macro ‘SZ’
  122 |                 rep(i,SZ(x)) node[i+n] = x[i];
      |                       ^~
answer.code:122:34: error: invalid types ‘int[ll {aka long long int}]’ for array subscript
  122 |                 rep(i,SZ(x)) node[i+n] = x[i];
      |                                  ^
answer.code:122:43: error: invalid types ‘const int[ll {aka long long int}]’ for array subscript
  122 |                 rep(i,SZ(x)) node[i+n] = x[i];
      |                                           ^
answer.code:123:31: error: invalid types ‘int[ll {aka long long int}]’ for array subscript
  123 |                 rrep(i,n) node[i] = compare(node[i*2], node[i*2+1]);
      |                               ^
answer.code:123:49: error: invalid types ‘int[ll {aka long long int}]’ for array subscript
  123 |                 rrep(i,n) node[i] = compare(node[i*2], node[i*2+1]);
      |                                                 ^
answer.code:123:60: error: invalid types ‘int[ll {aka long long int}]’ for array subscript
  123 |  ...