Submission #947234

#	Time	Username	Problem	Language	Result	Execution time	Memory
947234		borisAngelov	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	2234 ms	110928 KiB

nekameleoni

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int maxk = 51;

int n, k, q;

int a[maxn];

long long allset;

struct Node
{
    int minPos[maxk];
    int maxPos[maxk];
    long long mask;
    int ans;
};

Node tree[4 * maxn];

Node combine(const Node& nodeLeft, const Node& nodeRight)
{
    Node res;

    res.mask = (nodeLeft.mask | nodeRight.mask);
    res.ans = min(nodeLeft.ans, nodeRight.ans);

    for (int i = 0; i < k; ++i)
    {
        res.minPos[i] = min(nodeLeft.minPos[i], nodeRight.minPos[i]);
        res.maxPos[i] = max(nodeLeft.maxPos[i], nodeRight.maxPos[i]);
    }

    if (res.mask < allset)
    {
        res.ans = maxn;
        return res;
    }

    //cout << "do actual combine" << endl;

    vector<pair<int, int>> fromLeft;
    vector<pair<int, int>> fromRight;

    for (int i = 0; i < k; ++i)
    {
        if (nodeLeft.maxPos[i] != -maxn)
        {
            fromLeft.push_back(make_pair(nodeLeft.maxPos[i], i));
        }

        if (nodeRight.minPos[i] != +maxn)
        {
            fromRight.push_back(make_pair(nodeRight.minPos[i], i));
        }
    }

    sort(fromLeft.begin(), fromLeft.end());
    sort(fromRight.begin(), fromRight.end());

    /*cout << "Left " << endl;

    for (int i = fromLeft.size() - 1; i >= 0; --i)
    {
        cout << fromLeft[i].first << " " << fromLeft[i].second << endl;
    }

    cout << "----------------------" << endl;

    for (int i = 0; i < fromRight.size(); ++i)
    {
        cout << fromRight[i].first << " " << fromRight[i].second << endl;
    }

    cout << "----------------------" << endl;*/

    long long prefMask = 0;
    long long suffMask = 0;

    for (int j = 0; j < fromRight.size(); ++j)
    {
        suffMask |= (1LL << fromRight[j].second);
        //cout << "add to right " << fromRight[j].second << " " << suffMask << endl;
    }

    int ptr = fromRight.size() - 1;

    for (int i = fromLeft.size() - 1; i >= 0; --i)
    {
        prefMask |= (1LL << fromLeft[i].second);
        //cout << "add to left " << fromLeft[i].second << " " << prefMask << endl;

        while (ptr - 1 >= 0 && (prefMask | (suffMask ^ (1LL << fromRight[ptr].second))) == allset)
        {
            suffMask ^= (1LL << fromRight[ptr].second);
            //cout << "remove from right " << fromRight[ptr - 1].second << " " << suffMask << endl;
            --ptr;
        }

        if ((prefMask | suffMask) == allset)
        {
            //cout << "match " << i << " with " << ptr << " :: " << (prefMask | suffMask) << " :: " << prefMask << " " << suffMask << endl;
            res.ans = min(res.ans, fromRight[ptr].first - fromLeft[i].first + 1);
        }
    }

    return res;
}

void build(int node, int l, int r)
{
    if (l == r)
    {
        for (int i = 0; i < k; ++i)
        {
            tree[node].minPos[i] = +maxn;
            tree[node].maxPos[i] = -maxn;
        }
        tree[node].mask = (1LL << a[l]);
        tree[node].minPos[a[l]] = l;
        tree[node].maxPos[a[l]] = l;
        tree[node].ans = maxn;
        return;
    }

    int mid = (l + r) / 2;

    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);

    //cout << "combine for interval " << l << " to " << r << endl;
    tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
    //cout << "finish for interval " << l << " to " << r << endl;
}

void update(int node, int l, int r, int pos, int val)
{
    if (l == r)
    {
        tree[node].mask = 0;
        tree[node].minPos[a[l]] = +maxn;
        tree[node].maxPos[a[l]] = -maxn;
        a[l] = val;
        tree[node].mask = (1LL << a[l]);
        tree[node].minPos[a[l]] = pos;
        tree[node].maxPos[a[l]] = pos;
        return;
    }

    int mid = (l + r) / 2;

    if (pos <= mid)
    {
        update(2 * node, l, mid, pos, val);
    }
    else
    {
        update(2 * node + 1, mid + 1, r, pos, val);
    }

    tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        --a[i];
    }

    if (k == 1)
    {
        for (int i = 1; i <= q; ++i)
        {
            int type;
            cin >> type;

            if (type == 1)
            {
                int pos, val;
                cin >> pos >> val;
            }
            else
            {
                cout << "0\n";
            }
        }

        return 0;
    }

    allset = (1LL << k) - 1;

    build(1, 1, n);

    for (int i = 1; i <= q; ++i)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            --val;
            update(1, 1, n, pos, val);
        }
        else
        {
            if (tree[1].mask != allset)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << tree[1].ans << "\n";
            }
        }
    }

    return 0;
}

Compilation message (stderr)

nekameleoni.cpp: In function 'Node combine(const Node&, const Node&)':
nekameleoni.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int j = 0; j < fromRight.size(); ++j)
      |                     ~~^~~~~~~~~~~~~~~~~~

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