Submission #898957

#	Time	Username	Problem	Language	Result	Execution time	Memory
898957		efedmrlr	Sequence (APIO23_sequence)	C++17	0 / 100	392 ms	60496 KiB

sequence

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

#include "sequence.h"
using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)



void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int N,m,q;

struct Node {
    int mn, mx, tag;
    Node() : mn(INF), mx(-INF), tag(0) {};
    Node(int v) : mn(v), mx(v), tag(0) {};
    Node merge(Node &oth) {
        Node ret;
        ret.mx = max(oth.mx, mx);
        ret.mn = min(oth.mn, mn);
        return ret;
    }
    void add(int x) {   
        mn += x;
        mx += x;
        tag += x;
    }
};

struct SegTree {
    vector<Node> data;
    int sz;
    SegTree() : sz(0) {}
    void reset(int s) {
        sz = s;
        data.assign(4*(sz + 3), Node());
    }
    void push(int v) {
        data[v<<1].add(data[v].tag);
        data[v<<1^1].add(data[v].tag);
        data[v].tag = 0;
    }

    void build(int tl, int tr, int v, vector<int> &vec) {
        if(tl == tr) {
            data[v] = Node(vec[tl]);
            return;
        }
        int tm = (tl + tr) >> 1;

        build(tl, tm, v<<1, vec);
        build(tm + 1, tr, v<<1^1, vec);
        data[v] = data[v<<1].merge(data[v<<1^1]);
    }

    int getMin(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v].mn;
        }
        if(tl > r || tr < l) return INF;
        int tm = (tl + tr) >> 1;
        push(v);
        return min(getMin(tl, tm, v<<1, l, r), getMin(tm + 1, tr, v<<1^1, l, r));
    }
    int getMin(int l, int r) {
        l = max(0, l); r = min(sz, r);
        if(l > r) return 0;
        return getMin(0, sz, 1, l, r);
    }

    int getMax(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v].mx;
        }
        if(tl > r || tr < l) return -INF;
        int tm = (tl + tr) >> 1;
        push(v);
        return min(getMax(tl, tm, v<<1, l, r), getMax(tm + 1, tr, v<<1^1, l, r));
    } 
    int getMax(int l, int r) {
        l = max(0, l); r = min(sz, r);
        if(l > r) return 0;
        return getMax(0, sz, 1, l, r);
    }

    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            data[v].add(val);
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        int tm = (tl + tr) >> 1;
        push(v);
        update(tl, tm, v<<1, l, r, val);
        update(tm + 1, tr, v<<1^1, l, r, val);
        data[v] = data[v<<1].merge(data[v<<1^1]);
    }
    void update(int l, int r, int val) {
        l = max(0, l); r = min(sz, r);
        if(l > r) return;
        update(0, sz, 1, l, r, val);
    }
};

SegTree st;
vector<vector<int> > occ; 
vector<int> pr;
int getSum(int l, int r) {
    l = max(0, l); r = min(N - 1, r);
    if(l > r) return 0;
    return st.getMax(r, r) - (l == 0 ? 0 : st.getMax(l - 1, l - 1));
} 
int sequence(int n, vector<int> a) {
    N = n;
    st.reset(n - 1);
    occ.assign(n + 1, vector<int>());
    pr.assign(n, 0);
    for(int i = 0; i<n; i++) {
        occ[a[i]].pb(i);
    } 
    pr[0] = 1;
    for(int i = 1; i<n; i++) pr[i] = pr[i - 1] + 1;
    st.build(0, n - 1, 1, pr);    
    

    for(int i = 1; i<=n; i++) {
        for(auto c : occ[i])  {
            st.update(c, n - 1, -1);
        }
        if(occ[i].size() > 1) {
            int fir = occ[i][0], sec = occ[i][1];
            int mx = st.getMax(sec + 1, n - 1) - st.getMin(0, fir - 1);
            int mn = st.getMin(sec + 1, n - 1) - st.getMax(0, fir - 1);
            if(mx >= -2 && mn <= 2) {
                return 2;
            }
        }
        for(auto c : occ[i]) {
            st.update(c, n - 1, -1);
        }
    }

    return 1;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18