Cod sursa(job #2636333)

Utilizator giotoPopescu Ioan gioto Data 17 iulie 2020 15:40:02
Problema Pedefe Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <bits/stdc++.h>
using namespace std;

const int DIM = 505;
const int INF = 1005;
const int MOD = 666013;

int n, m, p;
int dp[DIM][105];
int p1[DIM], p2[DIM];
int s1[DIM], s2[DIM], s3[105];

int aib[2][DIM][DIM];

void update(int l, int x, int y, int val) {
    ++x; ++y;
    for (int i = x; i <= n + 1 ; i += (i & (-i))) {
        for (int j = y; j <= m + 1 ; j += (j & (-j))) {
            aib[l][i][j] += val;
            if (aib[l][i][j] >= MOD) aib[l][i][j] -= MOD;
        }
    }
}

int query(int l, int x, int y) {
    int ans = 0;
    ++x; ++y;
    for (int i = x; i > 0 ; i -= (i & (-i))) {
        for (int j = y; j > 0 ; j -= (j & (-j))) {
            ans += aib[l][i][j];
            if (ans >= MOD) ans -= MOD;
        }
    }
    return ans;
}

bool cmp1(int x, int y) {
    if (s1[x] != s1[y]) return s1[x] < s1[y];
    return x < y;
}
bool cmp2(int x, int y) {
    if (s2[x] != s2[y]) return s2[x] < s2[y];
    return x < y;
}

int main()
{
    freopen("pedefe.in", "r", stdin);
    freopen("pedefe.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &p);

    for (int i = 1; i <= n ; ++i) scanf("%d", &s1[i]), p1[i] = i;
    for (int i = 1; i <= m ; ++i) scanf("%d", &s2[i]), p2[i] = i;
    for (int i = 1; i <= p ; ++i) scanf("%d", &s3[i]);

    sort(p1 + 1, p1 + n + 1, cmp1);
    sort(p2 + 1, p2 + m + 1, cmp2);

    s3[p + 1] = INF;
    update(0, 0, 0, 1);

    int Sol = 0;
    for (int k = 1, l = 0; k <= p + 1 ; ++k, l = 1 - l) {
        memset(aib[1 - l], 0, sizeof(aib[1 - l]));

        for (int i = 1; i <= n ; ++i) {
            if (s1[p1[i]] >= s3[k]) break ;
            for (int j = 1; j <= m ; ++j) {
                if (s2[p2[j]] >= s3[k]) break ;

                if (s1[p1[i]] == s2[p2[j]] && s1[p1[i]] >= s3[k - 1] && s1[p1[i]] < s3[k]) {
                    dp[p1[i]][p2[j]] = query(l, p1[i] - 1, p2[j] - 1);
                    update(l, p1[i], p2[j], dp[p1[i]][p2[j]]);
                }
            }
        }

        if (k == p + 1) {
            printf("%d", query(l, n, m));
            return 0;
        }

        for (int i = n; i >= 1 ; --i) {
            for (int j = m; j >= 1 ; --j) {
                if (s1[i] == s2[j] && s1[i] == s3[k]) {
                    dp[i][j] = query(l, i - 1, j - 1);
                    update(1 - l, i, j, dp[i][j]);
                }
            }
        }
    }


    return 0;
}