Submission #891339

#	Time	Username	Problem	Language	Result	Execution time	Memory
891339		TahirAliyev	Nekameleoni (COCI15_nekameleoni)	C++17	0 / 140	1597 ms	75732 KiB

nekameleoni

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 1e5 + 5;

int arr[MAX];
int n, k, m;

struct DATA{
    vector<int> locc, rocc;
    vector<ll> lmask, rmask;
    int ans = oo;
};

DATA tree[4 * MAX];

DATA comb(DATA a, DATA b){
    DATA c;
    
    bool mp[51];
    for(int id : a.locc){
        mp[arr[id]] = 1;
        c.locc.push_back(id);
    }
    for(int id : b.locc){
        if(!mp[arr[id]]){
            c.locc.push_back(id);
        }
    }
    bool mp2[51];
    for(int id : b.rocc){
        mp2[arr[id]] = 1;
        c.rocc.push_back(id);
    }
    for(int id : a.rocc){
        if(!mp2[arr[id]]){
            c.rocc.push_back(id);
        }
    }

    ll cr = 0;
    for(int id : c.locc){
        cr |= (1 << arr[id]);
        c.lmask.push_back(cr);
    }
    cr = 0;
    for(int id : c.rocc){
        cr |= (1 << arr[id]);
        c.rmask.push_back(cr);
    }

    c.ans = min(a.ans, b.ans);
    int S1 = a.rocc.size(), S2 = b.locc.size();
    int p1 = 0, p2 = S2 - 1;
    while(p2 >= 0 && p1 < S1){
        ll ms = a.rmask[p1] | b.lmask[p2];
        if(ms == (1 << k) - 1){
            c.ans = min(c.ans, -a.rocc[p1] + b.locc[p2] + 1 );
            p2--;
        }
        else{
            p1++;
        }
    }
    return c;
}

void build(int node, int l, int r){
    if(l == r){
        tree[node] = {{l}, {l}, {1 << arr[l]}, {1 << arr[l]}};
        return;
    }   
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

void update(int node, int l, int r, int pos){
    if(l == r){
        tree[node] = {{l}, {l}, {1 << arr[l]}, {1 << arr[l]}};
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) update(2 * node, l, mid, pos);
    else update(2 * node + 1, mid + 1, r, pos);
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

int main(){
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        arr[i]--;
    }
    build(1, 1, n);
    while(m--){
        int t; cin >> t;
        if(t == 1){
            int pos, val; cin >> pos >> val;
            val--;
            if(k == 1) continue;
            arr[pos] = val;
            update(1, 1, n, pos);
        }
        else{
            if(k == 1) cout << "1\n";
            else cout << ((tree[1].ans == oo)? -1 : tree[1].ans) << '\n';
        }
    }
}

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