oj.uz

Submission #132631

# Submission time Handle Problem Language Result Execution time Memory
132631 2019-07-19T09:01:15 Z patrikpavic2 Matching (CEOI11_mat) C++17
100 / 100
 1096 ms 40376 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e6 + 500;
const int BS = 1001347;
const int MOD = 1e9 + 7;


inline int add(const int &A, const int &B){
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int sub(const int &A, const int &B){
	if(A - B < 0) return A - B + MOD;
	return A - B;
}

inline int mul(const int &A, const int &B){
	return (ll)A * B % MOD;
}

int loga[N][2], pot[N], n, m, A[N], P[N];
vector < int > saz;

void add(int i,int k, int x){
	int fl = 0;
	if(x < 0) x *= -1, fl = 1;
	for(; i < N; i += i & -i){
		if(fl) loga[i][k] = sub(loga[i][k], x);
		else   loga[i][k] = add(loga[i][k], x);
	}
}

int query(int i,int k){
	int ret = 0;
	for(; i ; i -= i & -i)
		ret = add(ret, loga[i][k]);
	return ret;
}

int main(){
	scanf("%d%d", &m, &n);
	for(int i = 1;i <= m;i++){
		int x; scanf("%d", &x); 
		P[x - 1] = i;
	}
	for(int i = 0;i < n;i++){
		scanf("%d", A + i);
		saz.PB(A[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < n;i++){
		A[i] = lower_bound(saz.begin(), saz.end(), A[i]) - saz.begin() + 1;
	}	
	pot[0] = 1;
	for(int i = 1;i < n;i++){
		pot[i] = mul(pot[i - 1], BS);
	}
	int traz = 0;
	for(int i = 0;i < m;i++){
		traz = add(traz, mul(pot[i], i - query(P[i], 0)));
		add(P[i], 0, 1);
	}
	memset(loga, 0, sizeof(loga));
	int cur = 0;
	vector < int > sol;
	for(int i = 0;i < n;i++){
		if(i >= m){
			add(A[i - m], 0, -1);
			add(A[i - m], 1, -pot[i - m]);
			cur = sub(cur, query(A[i - m], 1));
		}
		cur = add(cur, mul(pot[i], min(i, m - 1) - query(A[i], 0)));
		add(A[i], 0, 1); 
		add(A[i], 1, pot[i]);
		if(i >= m - 1){
			if(mul(traz, pot[i - m + 1]) == cur)
				sol.PB(i - m + 2);
		}
	}
	printf("%d\n", (int)sol.size());
	for(int x : sol)
		printf("%d ", x);
	printf("\n");
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); 
          ~~~~~^~~~~~~~~~
mat.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8632 KB Output is correct
2 Correct 19 ms 8696 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8696 KB Output is correct
2 Correct 19 ms 8696 KB Output is correct
3 Correct 10 ms 8312 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 12008 KB Output is correct
2 Correct 101 ms 11880 KB Output is correct
3 Correct 157 ms 13052 KB Output is correct
4 Correct 158 ms 13064 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 12688 KB Output is correct
2 Correct 174 ms 12620 KB Output is correct
3 Correct 121 ms 12908 KB Output is correct
4 Correct 111 ms 14108 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 12896 KB Output is correct
2 Correct 112 ms 12336 KB Output is correct
3 Correct 138 ms 12524 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 31676 KB Output is correct
2 Correct 1096 ms 40376 KB Output is correct
3 Correct 581 ms 25180 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 30956 KB Output is correct
2 Correct 793 ms 26764 KB Output is correct
3 Correct 1028 ms 36828 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 29532 KB Output is correct
2 Correct 516 ms 37716 KB Output is correct
3 Correct 747 ms 29908 KB Output is correct
4 Correct 613 ms 38496 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 30300 KB Output is correct
2 Correct 702 ms 30600 KB Output is correct
3 Correct 266 ms 18848 KB Output is correct
4 Correct 727 ms 38408 KB Output is correct