oj.uz

Submission #899022

# Submission time Handle Problem Language Result Execution time Memory
899022 2024-01-05T10:58:42 Z efedmrlr Sequence (APIO23_sequence) C++17
0 / 100
 389 ms 58964 KB 
// #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;
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 , n - 1) - st.getMin(0, fir - 1);
            int mn = st.getMin(sec , n - 1) - st.getMax(0, fir - 1);
            // cout<<"i:"<<i<<" mn: "<<mn<<" mx:"<<mx<<"\n";

            if(mx >= -2 && mn <= 2) {
                return 2;
            }
        }
        for(auto c : occ[i]) {
            st.update(c, n - 1, -1);
        }
    }

    return 1;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 73 ms 51276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 57180 KB Output is correct
2 Correct 366 ms 58964 KB Output is correct
3 Correct 140 ms 58604 KB Output is correct
4 Correct 129 ms 58200 KB Output is correct
5 Incorrect 389 ms 55064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -