oj.uz

답안 #263058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
263058 2020-08-13T12:42:02 Z NONAME Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 2830 ms 47096 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 500;

int n, m, k;
int a[N];

struct tree {
    tree *L, *R;
    int val;
    vector <pair <ll, int> > pf, sf;

    tree () {
        val = 1e9;
        pf.clear();
        sf.clear();
    }

    pair <pair <vector <pair <ll, int> >, vector <pair <ll, int> > >, int> combine(tree *lft, tree *rgt) {
        vector <pair <ll, int> > res_pf, res_sf;
        int cur_val = 1e9;

        vector <pair <ll, int> > left, right;
        left = (lft -> pf);
        right = (rgt -> pf);
                   
        res_pf = left;
        for (int i = 0; i < int(right.size()); ++i)
            if ((res_pf.back().first | right[i].first) != res_pf.back().first)
                res_pf.push_back(make_pair(res_pf.back().first | right[i].first, right[i].second));

        left = (lft -> sf);
        right = (rgt -> sf);
        res_sf = right;
        for (int i = 0; i < int(left.size()); ++i)
            if ((res_sf.back().first | left[i].first) != res_sf.back().first)
                res_sf.push_back(make_pair(res_sf.back().first | left[i].first, left[i].second));

        left = (lft -> sf);
        right = (rgt -> pf);
        cur_val = min(lft -> val, rgt -> val);
        int p = int(right.size()) - 1;
        for (int i = 0; i < int(left.size()); ++i) {
            while (p >= 0 && (left[i].first | right[p].first) == (1ll << k) - 1)
                --p;

            if (p + 1 < int(right.size()) && (left[i].first | right[p + 1].first) == (1ll << k) - 1)
                cur_val = min(cur_val, right[p + 1].second - left[i].second + 1);
        }

        return make_pair(make_pair(res_pf, res_sf), cur_val);
    }
    
    void build(int l, int r) {
        if (l > r)
            return;

        if (l == r) {
            val = 1e9;
            if (k == 1)
                val = 1;
            pf.push_back(make_pair((1ll << a[l]), l));
            sf.push_back(make_pair((1ll << a[l]), l));
            return;
        }

        int md = (l + r) >> 1;

        L = new tree();
        R = new tree();

        L -> build(l, md);
        R -> build(md + 1, r);
        
        auto cur = combine(L, R);

        pf = cur.first.first;
        sf = cur.first.second;
        val = cur.second;
    }

    void upd(int l, int r, int p, int v) {
        if (l == r) {
            val = 1e9;
            
            if (k == 1)
                val = 1;
            a[l] = v;
            
            pf[0] = sf[0] = make_pair((1ll << a[l]), l);
            return;
        }

        int md = (l + r) >> 1;

        if (p <= md) L -> upd(l, md, p, v);
            else R -> upd(md + 1, r, p, v);

        auto cur = combine(L, R);

        pf = cur.first.first;
        sf = cur.first.second;
        val = cur.second;
    }

    /*void show(int l, int r) {
        if (l > r)
            return;

        cerr << l + 1 << " " << r + 1 << "\n";
        cerr << val << "\n";
        for (int i = 0; i < int(pf.size()); ++i)
            cerr << pf[i].first << " " << pf[i].second << "\n";
        cerr << "---\n";
        for (int i = 0; i < int(sf.size()); ++i)
            cerr << sf[i].first << " " << sf[i].second << "\n";
        cerr << "!--------------\n\n";

        if (l == r)
            return;

        int md = (l + r) >> 1;
        L -> show(l, md);
        R -> show(md + 1, r);
    }*/
};

int main() {  
    cin >> n >> k >> m;
    for (int i = 0; i < n; ++i)
        cin >> a[i], --a[i];

    tree t;
    t.build(0, n - 1);
    //t.show(0, n - 1);

    for (int i = 0; i < m; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int p, v;
            cin >> p >> v;
            --p; --v;
            t.upd(0, n - 1, p, v);
        } else cout << (t.val == 1e9 ? -1 : t.val) << "\n";
    }
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 2296 KB Output is correct
2 Correct 76 ms 2216 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 2728 KB Output is correct
2 Correct 95 ms 2680 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 836 ms 10488 KB Output is correct
2 Correct 2676 ms 33120 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1295 ms 25872 KB Output is correct
2 Correct 2639 ms 43784 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1685 ms 20340 KB Output is correct
2 Correct 2729 ms 38212 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1948 ms 31356 KB Output is correct
2 Correct 2788 ms 40088 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2009 ms 28964 KB Output is correct
2 Correct 2805 ms 42340 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2496 ms 46972 KB Output is correct
2 Correct 2830 ms 46520 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2388 ms 47096 KB Output is correct
2 Correct 2746 ms 46300 KB Output is correct