oj.uz

Submission #891331

# Submission time Handle Problem Language Result Execution time Memory
891331 2023-12-22T19:06:05 Z TahirAliyev Nekameleoni (COCI15_nekameleoni) C++17
0 / 140
 1528 ms 76720 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];
    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)) - 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;
    k--;
    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) continue;
            arr[pos] = val;
            update(1, 1, n, pos);
        }
        else{
            if(!k) cout << "1\n";
            else cout << ((tree[1].ans == oo)? -1 : tree[1].ans) << '\n';
        }
    }
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 42076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 42332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 42844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 48528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 836 ms 60684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1119 ms 56172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1363 ms 64264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1241 ms 62992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1496 ms 76628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1528 ms 76720 KB Output isn't correct
2 Halted 0 ms 0 KB -