oj.uz

Submission #652181

# Submission time Handle Problem Language Result Execution time Memory
652181 2022-10-21T15:37:56 Z ymm Lottery (CEOI18_lot) C++17
45 / 100
 3000 ms 29192 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace mmu {
	const int page_size = 128;
	const int page_cnt = 98304;
	short page[page_cnt][page_size];
	vector<int> free_pages;

	void init()
	{
		free_pages.resize(page_cnt);
		iota(free_pages.begin(), free_pages.end(), 0);
	}

	void free(short *p)
	{
		int i = (p - page[0]) / page_size;
		free_pages.push_back(i);
	}

	short *alloc()
	{
		if (free_pages.empty())
			return NULL;
		int ans = free_pages.back();
		free_pages.pop_back();
		return page[ans];
	}
}

struct list_node {
	short *page;
	int off;
	int nxt;
} list_pool[10000000];

int new_list_node()
{
	static int nxt = 1;
	return nxt++;
}

const int N = 10000;
const int Q = 100;
int mylist[N];
int n, q, l;

void pop_list(int i)
{
	mmu::free(list_pool[mylist[i]].page);
	mylist[i] = list_pool[mylist[i]].nxt;
}

short *list_page_alloc()
{
	static int p = 0;
	short *ans = mmu::alloc();
	if (ans) {
		return ans;
	} else {
		while (!mylist[p])
			++p;
		pop_list(p);
		return mmu::alloc();
	}
}

void make_list(int i)
{
	if (i % mmu::page_size == 0) {
		Loop (j,0,i) {
			if (mylist[j] && list_pool[mylist[j]].off < i)
				pop_list(j);
		}
	}
	mylist[i] = new_list_node();
	list_node *ls = &list_pool[mylist[i]];
	int off = i - i%mmu::page_size;
	for (;;) {
		ls->off = off;
		ls->page = list_page_alloc();
		off += mmu::page_size;
		if (off >= n-l+1)
			break;
		ls->nxt = new_list_node();
		ls = &list_pool[ls->nxt];
	}
}

short *get_from_list(int l, int i)
{
	if (!mylist[l])
		return NULL;
	list_node *p = &list_pool[mylist[l]];
	if (p->off > i)
		return NULL;
	for (;;) {
		if (i < p->off + mmu::page_size)
			return &p->page[i - p->off];
		if (!p->nxt)
			return NULL;
		p = &list_pool[p->nxt];
	}
}

int noncmp_a[N];
short a[N];

short get_sim(int i, int j, int l)
{
	short ans = 0;
	for (int k = 0; k < l; ++k)
		ans += a[i+k] != a[j+k];
	return ans;
}

short sim_cnt[N+1];
short sim_pre[N+2];
short ans[Q][N];
short query[Q];

void process(int i)
{
	memset(sim_cnt, 0, sizeof(sim_cnt));
	make_list(i);
	Loop (j,0,i) {
		short *x = get_from_list(j, i);
		if (x)
			sim_cnt[*x]++;
		else
			sim_cnt[get_sim(i, j, l)]++;
	}
	Loop (j,i+1,n-l+1) {
		short x = get_sim(i, j, l);
		*get_from_list(i, j) = x;
		sim_cnt[x]++;
	}
	sim_pre[0] = 0;
	Loop (j,0,l+1)
		sim_pre[j+1] = sim_pre[j] + sim_cnt[j];
	Loop (j,0,q)
		ans[j][i] = sim_pre[query[j]+1];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	vector<int> cmper;
	cin >> n >> l;
	Loop (i,0,n) {
		cin >> noncmp_a[i];
		cmper.push_back(noncmp_a[i]);
	}
	cin >> q;
	Loop (i,0,q)
		cin >> query[i];
	sort(cmper.begin(), cmper.end());
	cmper.resize(unique(cmper.begin(), cmper.end()) - cmper.begin());
	Loop (i,0,n) {
		a[i] = lower_bound(cmper.begin(), cmper.end(),
		                   noncmp_a[i]) - cmper.begin();
	}
	mmu::init();
	Loop (i,0,n)
		process(i);
	Loop (i,0,q) {
		Loop (j,0,n-l+1)
			cout << ans[i][j] << ' ';
		cout << '\n';
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 5 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 5 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 78 ms 3412 KB Output is correct
14 Correct 928 ms 2368 KB Output is correct
15 Correct 965 ms 2196 KB Output is correct
16 Correct 399 ms 3028 KB Output is correct
17 Correct 532 ms 3012 KB Output is correct
18 Correct 523 ms 2972 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 29192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3065 ms 29192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 5 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 78 ms 3412 KB Output is correct
14 Correct 928 ms 2368 KB Output is correct
15 Correct 965 ms 2196 KB Output is correct
16 Correct 399 ms 3028 KB Output is correct
17 Correct 532 ms 3012 KB Output is correct
18 Correct 523 ms 2972 KB Output is correct
19 Execution timed out 3065 ms 29192 KB Time limit exceeded
20 Halted 0 ms 0 KB -