oj.uz

답안 #891348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891348 2023-12-22T19:21:00 Z TahirAliyev Nekameleoni (COCI15_nekameleoni) C++17
14 / 140
 1705 ms 80320 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 |= (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
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 42072 KB Output is correct
2 Correct 33 ms 42080 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 42584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 43012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 531 ms 49356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 814 ms 61900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1101 ms 57352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1327 ms 65224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1363 ms 63724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1705 ms 80016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1622 ms 80320 KB Output isn't correct
2 Halted 0 ms 0 KB -