oj.uz

Submission #891339

# Submission time Handle Problem Language Result Execution time Memory
891339 2023-12-22T19:10:24 Z TahirAliyev Nekameleoni (COCI15_nekameleoni) C++17
0 / 140
 1597 ms 75732 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){
            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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 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 481 ms 48236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

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

Subtask #9
0 / 14.0

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

Subtask #10
0 / 14.0

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