Submission #1268297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268297		dex111222333444555	Nautilus (BOI19_nautilus)	C++20	0 / 100	112 ms	141120 KiB

nautilus

#include <bits/stdc++.h>
#define dbg(x) "[" << #x << " = " << x << "]"
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 5, MAXV = 1e6 + 6, MOD = 1e9 + 7;
int numVal, val[MAXN], len, numQuery;

struct segmentTree{
    int n;
    vector<int> mx, lazy;
    segmentTree(int _n = 0): n(_n){
        mx.assign(n << 2 | 1, 0);
        lazy.assign(n << 2 | 1, 0);
    }
    void push(int id, int l, int r){
        if (!lazy[id]) return;
        mx[id] += lazy[id];
        if (l != r){
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, int val){
        push(id, l, r);
        if (l > r || l > v || r < u || u > v) return;
        if (l >= u && r <= v){
            lazy[id] += val;
            push(id, l, r);
            return;
        }
        int m = (l + r) >> 1;
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);
        mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
    }
    void update(int u, int v, int val){
        update(1, 1, n, u, v, val);
    }
    int get(int id, int l, int r, int u, int v){
        push(id, l, r);
        if (l > r || l > v || r < u || u > v) return 0;
        if (l >= u && r <= v) return mx[id];
        int m = (l + r) >> 1;
        return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }
    int get(int u, int v){
        return get(1, 1, n, u, v);
    }
};

set<int> st[MAXV];

void input(){
    cin >> numVal >> numQuery >> len;
    for(int i = 1; i <= numVal; i++) cin >> val[i];
}

void solve(){
    map<int, int> mark;
    for(int i = 1; i <= len; i++) mark[val[i]]++;

    segmentTree myIt(numVal - len + 1);
    myIt.update(1, 1, (int)mark.size());
    for(int i = 2; i <= numVal - len + 1; i++){
        mark[val[i - 1]]--;
        if (mark[val[i - 1]] == 0) mark.erase(val[i - 1]);
        mark[val[i + len - 1]]++;
        myIt.update(i, i, (int)mark.size());
    }

    for(int i = 1; i < MAXV; i++) st[i].insert(0), st[i].insert(numVal + 1);
    for(int i = 1; i <= numVal; i++) st[val[i]].insert(i);

    while(numQuery--){
        int type, l, r, pos, x;
        cin >> type;
        if (type == 2){
            cin >> l >> r;
            cout << myIt.get(l, r - len + 1) << '\n';
        }else{
            cin >> pos >> x;
            if (val[pos] == x) continue;

            set<int>::iterator it = st[val[pos]].upper_bound(pos);
            set<int>::iterator it2 = it; it2--; it2--;
            int L = max(max(1, pos - len + 1), (*it2) + 1), R = min(min(numVal, pos), (*it) - len);
            myIt.update(L, R, -1);
            st[val[pos]].erase(pos);

            it = st[x].upper_bound(pos);
            it2 = it; it2--;
            L = max(max(1, pos - len + 1), (*it2) + 1), R = min(min(numVal, pos), (*it) - len);
            myIt.update(L, R, 1);
            st[x].insert(pos); val[pos] = x;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("OBSERVE.inp", "r")){
        freopen("OBSERVE.inp", "r", stdin);
        freopen("OBSERVE.out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while(t--){
        input();
        solve();
    }
    cerr << TIME << ".s\n";
}

Compilation message (stderr)

nautilus.cpp: In function 'int main()':
nautilus.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("OBSERVE.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
nautilus.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("OBSERVE.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 29
• Subtask 2: 0 / 37
• Subtask 3: 0 / 34