Submission #1306768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306768		DangKhoizzzz	Nekameleoni (COCI15_nekameleoni)	C++20	0 / 140	278 ms	589824 KiB

nekameleoni

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 4*2e5; 

int n, k, m;
int limit; 

struct node{
    int mxp[55], mnp[55], ans; 
    node()
    {
        for(int i = 0; i < 55; i++)
        {
            mxp[i] = -INF;
            mnp[i] = INF;
        }
        ans = INF;
    }
};

node st[maxn]; 
node join(const node &L, const node &R){
    node res;
    res.ans = min(L.ans, R.ans);
    bool full = 1;
    int need = (1ll << k) - 1, mask = 0;
    vector <pii> a, b;
    a.reserve(k); b.reserve(k);

    for(int i = 0; i < k; i++)
    {
        res.mxp[i] = max(L.mxp[i], R.mxp[i]);
        res.mnp[i] = min(L.mnp[i], R.mnp[i]);
        if (L.mxp[i] != -INF) a.push_back({L.mxp[i], i});
        if (R.mnp[i] != INF)  b.push_back({R.mnp[i], i});
        
        if(res.mxp[i] == -INF) full = 0;
        if(L.mxp[i] != -INF) mask |= (1ll << i);
    }

    if(!full) return res;
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int pos = 0, save = 0;
    for(int i = 0; i < a.size(); i++)
    {
        while((mask|save) != need && pos < b.size())
        {
            save |= (1ll << b[pos].se);
            pos++;
        }
        if(pos != 0 && (mask|save) == need)
        {
            res.ans = min(res.ans, b[pos-1].fi - a[i].fi + 1);
        }
        mask ^= (1ll << a[i].se);
    }
    return res;
}

void update(int pos, int val){
    int idx = pos + limit - 1; 
    
    st[idx] = node();
    st[idx].mxp[val] = pos;
    st[idx].mnp[val] = pos;
    for (idx /= 2; idx >= 1; idx /= 2){
        st[idx] = join(st[2 * idx], st[2 * idx + 1]);
    }
}

void solve()
{
    cin >> n >> k >> m;
    limit = 1;
    while(limit < n) limit <<= 1;
    for(int i = 1; i <= n; i++)
    {
        int x; cin >> x; x--; 
        int idx = i + limit - 1;
        st[idx] = node();
        st[idx].mxp[x] = i;
        st[idx].mnp[x] = i;
    }
    for(int i = limit - 1; i >= 1; i--) 
    {
        st[i] = join(st[2 * i], st[2 * i + 1]);
    }
    while(m--)
    {
        int t; cin >> t;
        if(t == 1)
        {
            int p , v; cin >> p >> v; v--;
            update(p, v);
        }
        else 
        {
            if(k == 1) cout << 1 << '\n';
            else cout << (st[1].ans == INF ? -1 : st[1].ans) << '\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout);
    solve();
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14