Submission #696120

#	Time	Username	Problem	Language	Result	Execution time	Memory
696120		Nhoksocqt1	Nekameleoni (COCI15_nekameleoni)	C++17	140 / 140	1417 ms	39432 KiB

nekameleoni

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int readInt() {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}

	if(ch == '-') minus = true; else result = ch - '0';
	while(true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}

	if(minus)
		return -result;
	else
		return result;
}

const int MAXN = 100005;

struct SegNode {
    vector<int> pre, suf;
    int best;
} seg[4 * MAXN];

int val[MAXN], cnt[MAXN], nArr, k, numQuery;

void mergeNode(SegNode &res, const SegNode &a, const SegNode &b) {
    res.pre = a.pre, res.suf = b.suf;
    res.best = min(a.best, b.best);

    for (int i = 1; i <= k; ++i)
        cnt[i] = 0;

    for (int it = 0; it < int(a.pre.size()); ++it)
        cnt[val[a.pre[it]]] = 1;

    for (int it = 0; it < int(b.pre.size()); ++it) {
        if(!cnt[val[b.pre[it]]]) {
            cnt[val[b.pre[it]]] = 1;
            res.pre.push_back(b.pre[it]);
        }
    }

    if(res.pre.size() == k)
        res.best = min(res.best, res.pre.back() - res.pre[0] + 1);

    for (int i = 1; i <= k; ++i)
        cnt[i] = 0;

    for (int it = 0; it < int(b.suf.size()); ++it)
        cnt[val[b.suf[it]]] = 1;

    for (int it = 0; it < int(a.suf.size()); ++it) {
        if(!cnt[val[a.suf[it]]]) {
            cnt[val[a.suf[it]]] = 1;
            res.suf.push_back(a.suf[it]);
        }
    }

    if(res.suf.size() == k)
        res.best = min(res.best, res.suf[0] - res.suf.back() + 1);

    for (int i = 1; i <= k; ++i)
        cnt[i] = 0;

    for (int it = 0; it < int(b.pre.size()); ++it)
        ++cnt[val[b.pre[it]]];

    int cntNum(b.pre.size()), j(int(b.pre.size()) - 1);
    for (int it = 0; it < int(a.suf.size()); ++it) {
        cntNum += (++cnt[val[a.suf[it]]] == 1);
        while(j >= 0 && cntNum == k && cnt[val[b.pre[j]]] > 1) {
            --cnt[val[b.pre[j]]];
            --j;
        }

        if(cntNum == k) {
            res.best = min(res.best, (j >= 0 ? b.pre[j] : a.suf[0]) - a.suf[it] + 1);
            //cout << (j >= 0 ? b.pre[j] : a.suf[0]) << ' ' << a.suf[it] << '\n';
        }
    }

    //cout << res.best << '\n';
}

void build(int id, int l, int r) {
    if(l == r) {
        seg[id].pre.push_back(l);
        seg[id].suf.push_back(l);
        seg[id].best = (k == 1) ? 1 : 1e9+7;
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    //cout << l << ' ' << r << ":\n";
    mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
}

void update(int pos, int val) {
    int id(1), l(1), r(nArr);
    while(l != r) {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }
    }

    while(id > 1) {
        id >>= 1;
        mergeNode(seg[id], seg[id << 1], seg[id << 1 | 1]);
    }
}

void process() {
    cin >> nArr >> k >> numQuery;
    for (int i = 1; i <= nArr; ++i) {
        cin >> val[i];
    }

    build(1, 1, nArr);
    for (int t = 0; t < numQuery; ++t) {
        int type, pos, v;
        cin >> type;
        if(type == 1) {
            cin >> pos >> v;
            val[pos] = v;
            update(pos, v);
        } else {
            cout << (seg[1].best >= 1e9 ? -1 : seg[1].best) << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    process();
    return 0;
}

Compilation message (stderr)

nekameleoni.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
nekameleoni.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
nekameleoni.cpp: In function 'void mergeNode(SegNode&, const SegNode&, const SegNode&)':
nekameleoni.cpp:73:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     if(res.pre.size() == k)
      |        ~~~~~~~~~~~~~~~^~~~
nekameleoni.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |     if(res.suf.size() == k)
      |        ~~~~~~~~~~~~~~~^~~~

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