4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс, Актобе

Задача B. Array

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Дан массив $a$ длины $k$. Так же, имеются $n$ массивов длины $k$. Массив $x$ называется хорошим, если существует перестановка $p$ длины $k$, такая что для каждого $i$ $(1 <= i <= k)$ выполняется $x_{p_i} \equiv 0 \pmod{a_i}$. Вам необходимо посчитать количество пар $(l, r)$ $(1 <= l <= r <= n)$, таких что количество хороших массивов в отрезке больше чем нехороших.

Формат входного файла

В первой строке входных данных даются числа $n$ и $k$ $(1 <= n <= 10^5, 1 <= k <= 20)$. Во второй строке входных данных даётся массив $a$ длины $k$ $(1 <= a_i <= 10^9)$. В следующих $n$ строк даются массивы длины $k$, где в $i$-ой содержится массив $b_i$ $(1 <= b_{ij} <= 10^9,$ где $1 <= i <= k)$.

Формат выходного файла

В единственной строке выходных данных выведите одно число - ответ на задачу.

Система оценки

Данная задача содержит четыре подзадачи:

1. $1 <= n <= 1000, k = 1$. Оценивается в $15$ баллов.
2. $1 <= n <= 1000, 1 <= k <= 8$. Оценивается в $19$ баллов.
3. $1 <= n <= 100, 1 <= k <= 20$. Оценивается в $31$ баллов.
4. $1 <= n <= 10^5, 1 <= k <= 8$. Оценивается в $35$ баллов.

Пример:

Вход

3 1
2
1
2
2

Ответ

4

Замечание

$a \equiv 0 \pmod{b}$ - означает что число $a$ делится на $b$ без остатка. В первом тестовом примере, пары $(1, 1)$ и $(1, 2)$ не входят в ответ, так как в одном количество хороших массивов в одном равно $0$ $(0 <= 1)$, а во втором равно $1$ $(1 <= 1)$. ( Nurlykhan Kairly )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
//#include <algorithm>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 22
#define NN 100010
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define READ(f) freopen (f, "r", stdin)
#define WRITE(f) freopen (f, "w", stdout)
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n) for(int i = n - 1; i >= 0; --i)
#define forr1(i, n)	for(int i = n; i >= 1; --i)
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define elif else if
#define lld long double
#define r0 return 0
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int inf = 2e9;
const ll infl = 2e17;
const ll modw = 1e9 + 9;

const ll mods[2] = {(ll)1e9 + 7, (ll)1e9 + 9};
const ll p[2] = {31, 53};
const int K = 355;
const lld PI = acos(-1);

using namespace std;
//using namespace __gnu_pbds;

ll gcd(ll a1, ll b1)
{
	return b1?gcd(b1,a1%b1):a1;
}

ll binpow(ll a1, ll n1)
{
	if(n1 == 0)	return 1ll;
	if(n1 % 2 == 1)	return (binpow(a1, n1 - 1) * a1) % modw;
	else
	{
		ll b1 = binpow(a1, n1 >> 1ll);
		return (b1 * b1) % modw;
	}
}

vector<int> mt;
vector<bool> used;
vector<int> g[N];
int a[N], b[N];
int k;
bool ans[NN];
int pr[NN], inv[NN];
int ot[(NN << 2)];
int v[NN * 20];

bool try_kuhn(int x)
{
	if(used[x])	return 0;
	used[x] = 1;
	for(auto i:g[x])
	{
		if(mt[i] == -1)
		{
			mt[i] = x;
			return 1;
		}
	}
	for(auto i:g[x])
	{
		if(try_kuhn(mt[i]))
		{
			mt[i] = x;
			return 1;
		}
	}
	return 0;
}

void update(int l, int r, int u, int pos)
{
    if(l == r)
    {
        v[u]++;
        return;
    }
    int m = (l + r) >> 1;
    if(pos <= m)	update(l, m, u << 1, pos);
    else	update(m + 1, r, u << 1 | 1, pos);
    v[u] = v[u << 1] + v[u << 1 | 1];
}
int get(int l, int r, int l1, int r1, int u)
{
    if(r < l1 || r1 < l)	return 0;
    if(l1 <= l && r <= r1)	return v[u];
    int m = (l + r) >> 1;
    return get(l, m, l1, r1, u << 1) + get(m + 1, r, l1, r1, u << 1 | 1);
}

int main()
{
	barnarnar
	int n;
	cin >> n >> k;
	forn(i, k)	cin >> a[i];
	ll globalans = 0;
	int md1 = ((NN << 1) - 5);
	int md2 = ((NN << 2) - 3);
	update(1, md2, 1, md1);
	forn1(ii, n)
	{
		pr[ii] = pr[ii - 1];
		mt.assign(k, -1);
		forn(i, k)
		{
			g[i].clear();
			cin >> b[i];
			forn(j, k)	if(b[i] % a[j] == 0)	g[i].pb(j);
		}
		forn(i, k)
		{
			used.assign(k + 1, 0);
			try_kuhn(i);
		}
		int anss = 0;
		forn(i, k)	if(mt[i] != -1)	anss++;
		pr[ii] += (anss == k);
		int inv = (pr[ii] << 1) - ii + md1;
		update(1, md2, 1, inv);
		//cout << "check " << inv[ii] << endl;
		globalans += (get(1, md2, 1, inv - 1, 1) * 1ll);
		//cout << "ans " << globalans << endl;
	}
	cout << globalans;
	r0;
}
// #_# ok

показать/скрыть код

#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) for (int i = l; i != r; (l > r ? i-- : i++))
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
const int m = 100000;
int n, k, mt[25], a[25], p[100005], t[200005];
vector<int> g[25];
bitset<25> w;
ll ans;
void read(int &x) {
  int f = 1;
  x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
void upd(int a) {
  for (; a <= 200000; a += (a & -a)) t[a]++;
}
int get(int a) {
  int b = 0;
  for (; a > 0; a -= (a & -a)) b += t[a];
  return b;
}
bool kuhn(int v) {
  if (w[v]) return 0;
  w[v] = 1;
  for (auto to : g[v]) {
    if (mt[to] == -1) {
      mt[to] = v;
      return 1;
    }
  }
  for (auto to : g[v]) {
    if (kuhn(mt[to])) {
      mt[to] = v;
      return 1;
    }
  }
  return 0;
}
bool check() {
  for (int i = 0; i < k; i++) {
    int x;
    read(x);
    mt[i] = -1;
    g[i].clear();
    for (int j = 0; j < k; j++)
      if (!(x % a[j])) g[i].pb(j);
  }
  for (int i = 0; i < k; i++) {
    w.reset();
    if (!kuhn(i)) return 0;
  }
  return 1;
}
int main() {
  // code
  read(n), read(k);
  for (int i = 0; i < k; i++) read(a[i]);
  upd(m);
  for (int i = 0; i < n; i++) {
    p[i] = (i ? p[i - 1] : 0) + (check() ? 1 : -1);
    upd(p[i] + m);
    ans += get(p[i] + m - 1);
  }
  cout << ans;
  // endl
  return 0;
}