Submission #1187469

#TimeUsernameProblemLanguageResultExecution timeMemory
1187469nevuorigMatching (CEOI11_mat)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll int
#define ld long double
#define str string

#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()

#define in insert

#define fi first
#define se second

#define size size()

#define begin begin()
#define end end()
#define back back()
#define front front()
#define rend rend()
#define rbegin rbegin()


#define ret return

#define ull unsigned long long

#define all(a) a.begin , a.end

#define gcd __gcd

#define lcm(a , b) (a * b) / gcd(a , b)

#define friopen freopen ("exercise.in", "r", stdin); freopen("exercise.out", "w", stdout);

using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const ll mod = 1e9 + 7 , mod2 = 998244353 , N = 1e6 , inf = 0;
const ld esp = 0.0000001 , Pi = 3.1415926535897932384626433832795;


ll p[N + 12] , node[4 * N + 12] , s[4 * N + 12];

void update(ll ind , ll v , ll x = 1 , ll l = 1 , ll r = N)
{
	if (r < ind || l > ind) ret ;
	if (l == r)
	{
		// cout<<l<<endl;
		node[x] = v;
		s[x] = (v != 0);
		ret;
	}
	else
	{
		ll m = (l + r) / 2;
		update(ind , v , 2 * x , l , m);
		update(ind , v , 2 * x + 1 , m + 1 , r);
		node[x] = (node[2 * x]*1LL + (node[2 * x + 1]*1LL * p[s[2 * x]]%mod * 1LL) % mod) % mod;
		s[x] = s[2 * x] + s[2 * x + 1];
	}
}
ll a[N + 12] , b[N+12];
pair<ll , ll> b2[N + 12];
void kol_a()
{
  ll n , m , i , j;
  cin >> n >> m;
  deque<ll> ans;
  
  for (i = 1 ; i <= n ; i ++) cin >> a[i];
  for (i = 1 ; i <= m ; i ++)
  {
    cin >> b[i];
    b2[i] = {b[i] , i};
  }
  sort(b2 + 1 , b2 + 1+ m);
  for(i = 1 ; i <= m ; i ++) b[b2[i].se] = b2[i].fi;a

	for (i = 1 ; i <= n ; i ++)
	{
		v1 = (v1*1LL + (a[i] * 1LL*p[i - 1])%mod ) % mod;
		v2 = (v2*1LL +p[i - 1])%mod;
	}
	
	
	for (i = 1 ; i <= n ; i ++) update(b[i] , i);
	
	
	if (v1 == node[1]) ans.pb(1);
	
	for (i = 2 ; i + n - 1 <= m ; i ++)
	{
		update(b[i - 1] , 0);
		update(b[i + n - 1] , i + n - 1);
		v1 = (v1 + v2*1LL) % mod;
		if (v1 == node[1]){ ans.pb(i);}
	}
	cout << ans.size << '\n';
	for (auto x : ans) cout << x << " ";
	cout<<endl;
}


main()
{
	// friopen
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll _ = 1;

	
	
    while(_ --) kol_a();
}


/*



*/

Compilation message (stderr)

mat.cpp: In function 'void kol_a()':
mat.cpp:85:54: error: expected ';' before 'for'
   85 |   for(i = 1 ; i <= m ; i ++) b[b2[i].se] = b2[i].fi;a
      |                                                      ^
      |                                                      ;
   86 | 
   87 |         for (i = 1 ; i <= n ; i ++)
      |         ~~~                                           
mat.cpp:87:35: error: expected ';' before ')' token
   87 |         for (i = 1 ; i <= n ; i ++)
      |                                   ^
      |                                   ;
mat.cpp:97:13: error: 'v1' was not declared in this scope; did you mean '__pstl::execution::v1'?
   97 |         if (v1 == node[1]) ans.pb(1);
      |             ^~
      |             __pstl::execution::v1
In file included from /usr/include/c++/11/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from mat.cpp:1:
/usr/include/c++/11/pstl/execution_defs.h:19:18: note: '__pstl::execution::v1' declared here
   19 | inline namespace v1
      |                  ^~
mat.cpp:103:17: error: 'v1' was not declared in this scope; did you mean '__pstl::execution::v1'?
  103 |                 v1 = (v1 + v2*1LL) % mod;
      |                 ^~
      |                 __pstl::execution::v1
In file included from /usr/include/c++/11/pstl/glue_algorithm_defs.h:15,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from mat.cpp:1:
/usr/include/c++/11/pstl/execution_defs.h:19:18: note: '__pstl::execution::v1' declared here
   19 | inline namespace v1
      |                  ^~
mat.cpp:103:28: error: 'v2' was not declared in this scope; did you mean 'b2'?
  103 |                 v1 = (v1 + v2*1LL) % mod;
      |                            ^~
      |                            b2
mat.cpp: At global scope:
mat.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main()
      | ^~~~