제출 #347223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347223		kingfran1907	Matching (CEOI11_mat)	C++14	36 / 100	1969 ms	65540 KiB

mat

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int base = 1000133;
const int mod = 1e9+9;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
int a[maxn], b[maxn];
vector< int > v;
int pot[maxn];
map< int, vector< int > > ms;
int tour[treesiz], prop[treesiz];
int loga[maxn];

void updcnt(int x, int val) {
	for (x++; x < maxn; x += x & -x)
		loga[x] += val;
}

int ccnt(int x) {
	int out = 0;
	for (x++; x > 0; x -= x & -x)
		out += loga[x];
	return out;
}

int mul(int x, int y) {
	llint out = (llint)x * y;
	return out % mod;
}

int pote(int a, int b) {
	if (b == 0) return 1;
	else if (b % 2 == 1) return mul(a, pote(a, b - 1));
	else {
		int out = pote(a, b / 2);
		return mul(out, out);
	}
}

int inv(int x) {
	return pote(base, mod - 2);
}

void send(int node) {
	tour[node * 2] = mul(tour[node * 2], prop[node]);
	tour[node * 2 + 1] = mul(tour[node * 2 + 1], prop[node]);
	
	prop[node * 2] = mul(prop[node * 2], prop[node]);
	prop[node * 2 + 1] = mul(prop[node * 2 + 1], prop[node]);
	prop[node] = 1;
}

void update(int a, int b, int l, int r, int node, int val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node] = val;
		prop[node] = 1;
		return;
	}
	
	int mid = (l + r) / 2;
	send(node);
	update(a, b, l, mid, node * 2, val);
	update(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = (tour[node * 2] + tour[node * 2 + 1]) % mod;
}

int query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tour[node];
	
	int mid = (l + r) / 2;
	send(node);
	return (query(a, b, l, mid, node * 2) + query(a, b, mid + 1, r, node * 2 + 1));
}

void updat(int a, int b, int l, int r, int node, int val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node] = mul(tour[node], val);
		prop[node] = mul(prop[node], val);
		return;
	}
	
	int mid = (l + r) / 2;
	send(node);
	updat(a, b, l, mid, node * 2, val);
	updat(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = (tour[node * 2] + tour[node * 2 + 1]) % mod;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", a+i);
	for (int i = 0; i < m; i++) 
		scanf("%d", b+i);
	
	for (int i = 0; i < m; i++)
		v.push_back(b[i]);
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++) {
		b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
	}
	
	pot[0] = 1;
	for (int i = 1; i <= m; i++) pot[i] = mul(pot[i - 1], base);
	for (int i = 1; i < treesiz; i++) prop[i] = 1;
	
	llint has = 0;
	int divs = inv(base);
	assert(mul(base, divs) == 1);
	for (int i = 0; i <= m - n; i++) {
		if (i == 0) {
			for (int j = 0; j < n; j++) {
				updcnt(b[j], 1);
			}
			
			for (int j = 0; j < n; j++) {
				int tren = ccnt(b[j]) - 1;
				
				int ac = mul(j, pot[tren]);
				//printf("first %d(%d) %d -- %d (%d)\n", j, b[j], tren, pot[tren], ac);
				update(b[j], b[j], 0, off - 1, 1, ac);
				has += ac, has %= mod;
			}
			ms[has].push_back(0);
			assert(has == tour[1]);
		} else {
			int ac = b[i + n - 1];
			int cnt = ccnt(ac);
			//printf("i > 0: (%d) -> %d\n", ac, cnt);
			
			updcnt(ac, 1);
			update(ac, ac, 0, off - 1, 1, mul(i + n - 1, pot[cnt]));
			updat(ac + 1, off - 1, 0, off - 1, 1, base);
			
			int ths = tour[1];
			ms[ths].push_back(i);
		}
		//printf("debug: %d --> %d\n", i, tour[1]);
		
		update(b[i], b[i], 0, off - 1, 1, 0);
		//printf("fr: %d\n", tour[1]);
		updat(b[i] + 1, off - 1, 0, off - 1, 1, divs);
		updcnt(b[i], -1);
		//printf("after: %d --> %d\n", i, tour[1]);
	}
	
	has = 0;
	reverse(a, a + n);
	for (int i = 0; i < n; i++) {
		a[i]--;
		has = mul(has, base), has += a[i];
		has %= mod;
	}
	//printf("has == %d\n", has);
	
	int sum = 0;
	for (int i = 0; i < n; i++) sum += pot[i], sum %= mod;
	
	vector< int > sol;
	for (int i = 0; i <= m - n; i++) {
		vector< int > tren = ms[has];
		for (int j = 0; j < tren.size(); j++) {
			sol.push_back(tren[j]);
		}
		has += sum;
		has %= mod;
		//printf("sec has == %d\n", has);
	}
	
	printf("%d\n", sol.size());
	sort(sol.begin(), sol.end());
	for (int i = 0; i < sol.size(); i++) {
		printf("%d ", sol[i] + 1);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp: In function 'int main()':
mat.cpp:175:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |   for (int j = 0; j < tren.size(); j++) {
      |                   ~~^~~~~~~~~~~~~
mat.cpp:183:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  183 |  printf("%d\n", sol.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
mat.cpp:185:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |  for (int i = 0; i < sol.size(); i++) {
      |                  ~~^~~~~~~~~~~~
mat.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
mat.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%d", b+i);
      |   ~~~~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10