oj.uz

답안 #648194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
648194 2022-10-05T16:39:52 Z BackNoob Nekameleoni (COCI15_nekameleoni) C++14
140 / 140
 1534 ms 31720 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7; 
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int n;
int q;
int k;
int v[mxN];
map<ll, int> vis;
bool appear[mxN];

struct SegmentTree{
    struct Node{
        vector<int> pre;
        vector<int> suf;
        int best;
    };
    int n;
    vector<Node> t;

    SegmentTree(){}
    SegmentTree(int _n)
    {
        n = _n;
        int offset = 1;
        while(offset < n) offset *= 2;
        t.resize(offset * 2);
    }

    Node union_node(Node &a, Node &b, int le1, int le2)
    {
        Node res;

        for(int i = 1; i <= k; i++) appear[i] = false;
        res.pre = a.pre;
        for(auto it : res.pre) appear[v[it]] = true;
        for(auto it : b.pre) {
            if(sz(res.pre) == k) break;
            if(appear[v[it]] == false) {
                appear[v[it]] = true;
                res.pre.pb(it);
            }
        }

        for(int i = 1; i <= k; i++) appear[i] = false;
        res.suf = b.suf;
        for(auto it : res.suf) appear[v[it]] = true;
        for(auto it : a.suf) {
            if(sz(res.suf) == k) break;
            if(appear[v[it]] == false) {
                appear[v[it]] = true;
                res.suf.pb(it);
            }
        }

        // if(le1 + le2 == n) {
        //     for(auto it : a.suf) cout << it << ' ';
        //     cout << endl;
        //     for(auto it : b.pre) cout << it << ' ';
        //     cout << endl;
        // }

        res.best = inf;

        int j = sz(b.pre) - 1;
        ll rig = 0;
        ll lef = 0;
        ll fullmask = (1LL << k) - 1;
        for(auto it : b.pre) rig |= (1LL << (v[it] - 1));

        for(int i = 0; i < sz(a.suf); i++) {
            lef |= (1LL << (v[a.suf[i]] - 1));

            while(j > 0) {
                ll remask = (rig ^ (1LL << (v[b.pre[j]] - 1)));
                if((lef | remask) == fullmask) --j;
                else break;
                swap(rig, remask);
            }
            if((lef | rig) == fullmask) {
                minimize(res.best, b.pre[j] - a.suf[i] + 1);
            }
        }

        minimize(res.best, a.best);
        minimize(res.best, b.best);

        return res;
    }

    void build(int v, int tl, int tr)
    {
        if(tl == tr) {
            t[v].pre.pb(tl);
            t[v].suf.pb(tl);
            t[v].best = inf;
        }
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v] = union_node(t[v * 2], t[v * 2 + 1], tm - tl + 1, tr - tm);
        }
    }

    void update(int v, int tl, int tr, int pos, int val)
    {
        if(tl == tr) {
        }
        else {
            int tm = (tl + tr) / 2;
            if(pos <= tm) update(v * 2, tl, tm, pos, val);
            else update(v * 2 + 1, tm + 1, tr, pos, val);
            t[v] = union_node(t[v * 2], t[v * 2 + 1], tm - tl + 1, tr - tm);
        }
    }

    void update(int pos, int val)
    {
        update(1, 1, n, pos, val);
    }

} seg;



void solve()
{
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) cin >> v[i];

    seg = SegmentTree(n);
    seg.build(1, 1, n);

    while(q--) {
        int cmd;
        cin >> cmd;
        if(cmd == 1) {
            int pos, val;
            cin >> pos >> val;
            v[pos] = val;
            seg.update(pos, val);
        }
        else {
            int ans = seg.t[1].best;
            if(ans == inf) cout << -1 << endl;
            else cout << ans << endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1960 KB Output is correct
2 Correct 26 ms 1876 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2124 KB Output is correct
2 Correct 47 ms 2104 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 416 ms 7764 KB Output is correct
2 Correct 1192 ms 26760 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 589 ms 16844 KB Output is correct
2 Correct 1249 ms 30620 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 820 ms 15092 KB Output is correct
2 Correct 1280 ms 28480 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 971 ms 18840 KB Output is correct
2 Correct 1339 ms 29260 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 964 ms 18172 KB Output is correct
2 Correct 1318 ms 30016 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1129 ms 31576 KB Output is correct
2 Correct 1311 ms 31532 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1331 ms 31720 KB Output is correct
2 Correct 1534 ms 31436 KB Output is correct