oj.uz

Submission #891350

# Submission time Handle Problem Language Result Execution time Memory
891350 2023-12-22T19:26:18 Z TahirAliyev Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 1976 ms 80412 KB 
#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];
    memset(mp, 0, sizeof(mp));
    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);
        }
    }
    memset(mp, 0, sizeof(mp));
    for(int id : b.rocc){
        mp[arr[id]] = 1;
        c.rocc.push_back(id);
    }
    for(int id : a.rocc){
        if(!mp[arr[id]]){
            c.rocc.push_back(id);
        }
    }

    ll cr = 0;
    for(int id : c.locc){
        cr |= (1ll << arr[id]);
        c.lmask.push_back(cr);
    }
    cr = 0;
    for(int id : c.rocc){
        cr |= (1ll << 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 == (1ll << 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}, {1ll << arr[l]}, {1ll << 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}, {1ll << arr[l]}, {1ll << 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 42076 KB Output is correct
2 Correct 31 ms 42072 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42588 KB Output is correct
2 Correct 50 ms 42584 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 43096 KB Output is correct
2 Correct 71 ms 43100 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 49232 KB Output is correct
2 Correct 1647 ms 67988 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 62100 KB Output is correct
2 Correct 1799 ms 78424 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1131 ms 57428 KB Output is correct
2 Correct 1890 ms 73416 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1344 ms 65240 KB Output is correct
2 Correct 1976 ms 75152 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1302 ms 63736 KB Output is correct
2 Correct 1905 ms 77108 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1680 ms 79888 KB Output is correct
2 Correct 1902 ms 80412 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1651 ms 80064 KB Output is correct
2 Correct 1887 ms 80260 KB Output is correct