oj.uz

Submission #892191

# Submission time Handle Problem Language Result Execution time Memory
892191 2023-12-25T03:56:58 Z harao Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 22 ms 1884 KB 
#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[100];

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 --;
                    }
                    while(t < k && i1 <= n)
                    {
                        if(!cnt[a[i1]]) t ++;
                        cnt[a[i1]] ++;
                        i1 ++;
                    }
                    if(t == k) ans = min(ans, i1 - j);
                 }
                if(ans == 1e9 + 7) cout << -1 << "\n";
                else cout << ans << "\n";
            }
        }
    }
}

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 348 KB Output is correct
2 Correct 6 ms 344 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -