Submission #899038

#	Time	Username	Problem	Language	Result	Execution time	Memory
899038		efedmrlr	Sequence (APIO23_sequence)	C++17	100 / 100	984 ms	83992 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) {
          // cout<<"MIN:"<<l<<" "<<r<<" val:"<<0<<"\n";
          return 0;
        }
        // cout<<"MIN:"<<l<<" "<<r<<" val:"<<getMin(0, sz, 1, l, r)<<"\n";
        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 max(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) {
          // cout<<"MAX:"<<l<<" "<<r<<" val:"<<0<<"\n";
          return 0;
        }
        // cout<<"MAX:"<<l<<" "<<r<<" val:"<<getMax(0, sz, 1, l, r)<<"\n";
        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, st2;
vector<vector<int> > occ; 
vector<int> pr;

int sequence(int n, vector<int> a) {
    N = n;
    st.reset(n - 1); st2.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);   
    st2.build(0, n - 1, 1, pr); 
    int ans = 1;

    for(int v = 1; v<=n; v++) {
        for(auto c : occ[v]) {
            st2.update(c, n - 1, -2);
        }
        int l  = 0;
        for(int r = 0; r<occ[v].size(); r++) {
            while(l <= r) {
            int fir = occ[v][l], sec = occ[v][r];
            int v1 = st.getMax(sec, n - 1) - min(0, st.getMin(0, fir - 1));
            int v2 = st2.getMin(sec, n - 1) - max(0, st2.getMax(0, fir - 1));
            if(1ll * v1 * v2 <= 0ll) {
                ans = max(ans , r - l + 1);
                break;
            }
            l++;
            }
        }
        // cout<<"i:"<<i<<" mn: "<<mn<<" mx:"<<mx<<"\n";
 
        for(auto c : occ[v])  {
            st.update(c, n - 1, -2);
        }
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:154:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for(int r = 0; r<occ[v].size(); r++) {
      |                        ~^~~~~~~~~~~~~~

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