Submission #892188

#	Time	Username	Problem	Language	Result	Execution time	Memory
892188		harao	Nekameleoni (COCI15_nekameleoni)	C++17	28 / 140	23 ms	1884 KiB

nekameleoni

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
const int N = 1e5 + 7;
using ll = long long;
typedef pair<int, int> ii;

int n, k, Q;
int a[N], cnt[31];

struct query
{
    int type, id, x;
}q[N];

namespace sub1
{
    void solve()
    {
        for(int i = 1; i <= Q; i++)
        {
            if(q[i].type == 1) a[q[i].id] = q[i].x;
            else
            {
                for(int x = 1; x <= k; x ++) cnt[x] = 0;
                int i1 = 1;
                int t = 0;
                int ans = 1e9 + 7;
                for(int j = 1; j <= n; j++)
                {
                    if(j > 1)
                    {
                        cnt[a[j - 1]] --;
                        if(cnt[a[j - 1]] == 0) t --;
                    }
//                    if(j == 4) cout << cnt[3] << "\n";
                    while(t < k && i1 <= n)
                    {
                        if(!cnt[a[i1]]) t ++;
                        cnt[a[i1]] ++;
                        i1 ++;
                    }
                    if(t == k) ans = min(ans, i1 - j);
//                    cout << j << " " << i1 << " " << cnt[3] << "\n";
                 }
                if(ans == 1e9 + 7) cout << -1 << "\n";
                else cout << ans << "\n";
            }
        }
    }
}

//namespace sub2
//{
//
//
//    void solve()
//    {
//
//    }
//}
//
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(".inp","r",stdin);
//    freopen(".out","w",stdout);

    cin >> n >> k >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= Q; i++)
    {
        cin >> q[i].type;
        if(q[i].type == 1) cin >> q[i].id >> q[i].x;
    }

    if(n <= 5000 && Q <= 5000) sub1 :: solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 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