Submission #1370433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370433		gohchingjayk	Non-boring sequences (CERC12_D)	C++20	1 / 1	572 ms	115240 KiB

D

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

using ll = long long;

constexpr int INF = 1e9 + 5;
constexpr int MAXN = 200'000 + 5;

struct Node {
    Node *l = nullptr, *r = nullptr;
    int s, e, m;
    int v = 0;
    int lazy = 0;
    
    Node(int a, int b) {
        s = a; e = b;
        m = (s + e) / 2;
        
        if (s != e) {
            l = new Node(s, m);
            r = new Node(m+1, e);
        }
    }
    
    void prop() {
        if (!l) return;
        l->v += lazy;
        r->v += lazy;
        l->lazy += lazy;
        r->lazy += lazy;
        lazy = 0;
    }
    
    void range_add(int a, int b, int x) {
        if (e < a || b < s) return;
        if (a <= s && e <= b) {
            lazy += x;
            v += x;
            return;
        }
        
        prop();
        l->range_add(a, b, x);
        r->range_add(a, b, x);
        
        v = min(l->v, r->v);
    }
    
    int range_min(int a, int b) {
        if (e < a || b < s) return INF;
        if (a <= s && e <= b) return v;
        
        prop();
        v = min(l->v, r->v);
        return min(l->range_min(a, b), r->range_min(a, b));
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        
        vector<int> vals(N);
        
        for (int i = 0; i < N; ++i) cin >> vals[i];
        
        vector<int> disc = vals;
        sort(disc.begin(), disc.end());
        
        for (int i = 0; i < N; ++i) vals[i] = lower_bound(disc.begin(), disc.end(), vals[i]) - disc.begin();
        
        vector<int> prev(N);
        vector<int> last(N, -1);
        
        for (int i = 0; i < N; ++i) {
            prev[i] = last[vals[i]];
            last[vals[i]] = i;
        }
        
        Node *segtree = new Node(0, N-1);
        
        bool boring = false;
        for (int i = 0; i < N; ++i) {
            if (prev[i] != -1) {
                segtree->range_add(prev[prev[i]] + 1, prev[i], -1);
            }
            
            segtree->range_add(prev[i] + 1, i, 1);
            
            if (segtree->range_min(0, i) == 0) boring = true;
        }
        
        cout << (boring ? "boring" : "non-boring") << '\n';
    }
}

• Subtask 1: 1 / 1