Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

struct Node {
    int lastSum, minSum;

    Node(int lastSum = 0, int minSum = 0):
        lastSum (lastSum), minSum (minSum) {}
};

class SegmentTree {
    vector<Node> data;
    int n;

    void update(int k, int l, int r, int x, int delta) {
        if(!(l <= x && x < r)) return;
        if(l == x && r == x + 1) {
            data[k].lastSum += delta;
            data[k].minSum += delta;
        } else {
            int left = (k << 1) + 1, right = (k << 1) + 2, mid = (l + r) >> 1;
            update(left, l, mid, x, delta);
            update(right, mid, r, x, delta);
            data[k].lastSum = data[left].lastSum + data[right].lastSum;
            data[k].minSum = min(data[left].minSum, data[left].lastSum + data[right].minSum);
        }
    }

    public:
    SegmentTree(int n) {
        data.assign(4 * n, Node());
        this->n = n;
    }

    void update(int x, int delta) {
        update(0, 0, n, x, delta);
    }

    int getMinAll() const {
        return data[0].minSum;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<int> a (n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    SegmentTree tree (++m);
    tree.update(a[0], 1);
    tree.update(a[1] - 1, -1);
    int res = tree.getMinAll() == 0 ? 1 : -1;
    for(int i = 1; 2 * i + 1 < n; ++i) {
        tree.update(a[i] - 1, 1);
        tree.update(a[i], 1);
        tree.update(a[2 * i] - 1, -1);
        tree.update(a[2 * i + 1] - 1, -1);
        if(tree.getMinAll() == 0) res = i + 1;
    }
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define left k + k
#define right k + k + 1
#define mid (l + r >> 1)
const int N = 100005;
using namespace std;
int it[4 * N], lazy[4 * N], v[N], a[N];
int n, m;

void build(int k, int l, int r) {
    if (l > r) return;
    if (l == r) {it[k] = v[l]; return;}
    build(left, l, mid); build(right, mid + 1, r);
    it[k] = min(it[left], it[right]);
}

void diffuse(int k, int l, int r) {
    if (lazy[k] == 0) return;
    it[k] += lazy[k];
    if (l != r) {
        lazy[left] += lazy[k];
        lazy[right] += lazy[k];
    }
    lazy[k] = 0;
}

void upd(int k, int l, int r, int i, int j, int v) {
    diffuse(k, l, r);
    if (l > r || r < i || j < l) return;
    if (i <= l && r <= j) {lazy[k] = v; diffuse(k, l, r); return;}
    upd(left, l, mid, i, j, v); upd(right, mid + 1, r, i, j, v);
    it[k] = min(it[left], it[right]);
}

int get(int k, int l, int r, int i) {
    diffuse(k, l, r);
    if (l == r) return it[k];
    if (mid >= i) return get(left, l, mid, i);
    else return get(right, mid + 1, r, i);
}

void dbg() {
    for(int i = 1; i <= m; i++) printf("%d ", get(1, 1, m, i)); printf("\n");
}

int main()
{
    scanf("%d %d", &n, &m);
    int cen = n / 2;
    int i, k;
    for(i = 1; i <= n; i++) {
        scanf("%d", a + i);
        if (i <= cen) v[a[i]]++;
        else v[a[i] - 1]--;
    }
    for(i = 1; i <= m; i++) v[i] += v[i - 1];
    build(1, 1, m);
    //dbg();
    for(k = n / 2; k; k--) {
        if (it[1] >= 0) break;
        upd(1, 1, m, a[k], m, -1); //pop a[k] from the left
        upd(1, 1, m, a[k] - 1, m, -1); //push a[k] to the right
        upd(1, 1, m, a[k + k] - 1, m, 1); //pop the two rightmost out
        upd(1, 1, m, a[k + k - 1] - 1, m, 1);
        //dbg();
    }
    if (k == 0) k--;
    printf("%d", k);
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 100111;

int a[MN], c[MN], first[MN], last[MN];
int sum[MN*8], minsum[MN*8];
int n, m;

#define CT(x) ((x)<<1)
#define CP(x) (CT(x) + 1)

void update(int i, int l, int r, int u, int k) {
    if (u < l || r < u) return ;
    if (l == r) {
        sum[i] += k;
        minsum[i] = sum[i];
        return ;
    }
    int mid = (l + r) >> 1;
    update(CT(i), l, mid, u, k);
    update(CP(i), mid+1, r, u, k);

    sum[i] = sum[CT(i)] + sum[CP(i)];
    minsum[i] = min(minsum[CT(i)], sum[CT(i)] + minsum[CP(i)]);
}

int main() {
    GN(n); GN(m);
    FOR(i,1,n) {
        GN(a[i]);
        c[i] = a[i];
    }
    sort(c+1, c+n+1);

    FOR(i,1,n) last[c[i]] = i;
    FORD(i,n,1) first[c[i]] = i;

    int res = -1;
    FOR(i,1,n/2) {
        int ii = i << 1;
        if (i == 1) {
            update(1, 1, n, last[a[1]]--, 1);

            update(1, 1, n, first[a[2]]++, -1);
        }
        else {
            // Remove a[i] from second part
            update(1, 1, n, --first[a[i]], 1);

            // Add a[i] to first part
            update(1, 1, n, last[a[i]]--, 1);

            // Add a[ii-1] & a[ii-2] to second part
            update(1, 1, n, first[a[ii]]++, -1);
            update(1, 1, n, first[a[ii-1]]++, -1);
        }

        if (minsum[1] >= 0) {
            res = i;
        }
    }
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, 0, -1, +1};
const int dc[] = {-1, +1, 0, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = ld(1e-12);
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 100005

using namespace std;

int n, m, dt[maxn * 6] = {0}, f[maxn * 6] = {0}, a[maxn], g[maxn];

void updateMax(int id){
    f[id] = max(dt[2*id] + f[2*id], dt[2*id + 1] + f[2*id + 1]);
}

void updateValue(int id){
     dt[2*id] += dt[id];
     dt[2*id + 1] += dt[id];
     dt[id] = 0;
}

void update(int id,int l,int r,int u,int v,int add){
     int mid;
     if(u > r || v < l) return;
     if(u <= l && v >= r){
          dt[id] += add;
          return;
     }

     updateValue(id);   
     mid = (l + r) >> 1;
     update(2*id, l, mid, u, v, add);
     update(2*id + 1, mid + 1, r, u, v, add);
     updateMax(id);
}

int getmax(int id,int l,int r,int u,int v){
     int mid, t1, t2;
     if(u > r || v < l) return -inf;

     updateValue(id);
     if(u <= l && v >= r){
          updateMax(id); 
          return f[id];
     }

     mid = (l + r) >> 1;
     t1 = getmax(2*id , l, mid, u, v);
     t2 = getmax(2*id + 1, mid + 1, r, u, v);
     updateMax(id);
     return max(t1, t2);     
}

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    gi(n); gi(m);
    Rep(i, n) gi(a[i + 1]);
    //ms(dt, 0); ms(f, 0);
    int res = -1;
    update(1, 1, m + 1, a[1] + 1, m + 1, -1);
    update(1, 1, m + 1, a[2], m + 1, +1);
    if(getmax(1, 1, m + 1, 1, m + 1) <= 0) res = 1;
    For(i, 2, n / 2){
        update(1, 1, m + 1, a[i] + 1, m + 1, -1);
        update(1, 1, m + 1, a[i], m + 1, -1);
        update(1, 1, m + 1, a[i + i - 1], m + 1, 1);
        update(1, 1, m + 1, a[i + i], m + 1, 1);
        if(getmax(1, 1, m + 1, 1, m + 1) <= 0) res = i;
    }
    printf("%d\n", res);

   // cout << clock() << endl;
  //  getch();
}

Code mẫu của skyvn97

#include<cassert>
#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
using namespace std;
const int INF=(int)1e6+7;
class IT {
    private:
    vector<int> tree,lazy;
    int n;
    public:
    IT() {
        n=0;
        tree.clear();
        lazy.clear();
    }
    IT(int _n) {
        n=_n;
        tree=vector<int>(4*n+7,0);
        lazy=vector<int>(4*n+7,0);
    }
    private:
    void pushdown(int i) {
        tree[2*i]+=lazy[i];
        tree[2*i+1]+=lazy[i];
        lazy[2*i]+=lazy[i];
        lazy[2*i+1]+=lazy[i];
        lazy[i]=0;
    }
    void update(int i,int l,int r,int u,int v,int c) {
        if (l>v) return;
        if (r<u) return;
        if (l>r) return;
        if (v<u) return;
        if (u<=l && r<=v) {
            tree[i]+=c;
            lazy[i]+=c;
            return;
        }
        pushdown(i);
        int m=(l+r)/2;
        update(2*i,l,m,u,v,c);
        update(2*i+1,m+1,r,u,v,c);
        tree[i]=min(tree[2*i],tree[2*i+1]);
    }   
    public:
    void update(int val,int d) {
        update(1,1,n,1,val,d);
    }
    int getmin(void) const {        
        return (tree[1]);
    }   
};
int a[MAX];
int n;
IT it;
void init(void) {
    int m;
    scanf("%d",&n);
    scanf("%d",&m);
    it=IT(m);
    FOR(i,1,n) scanf("%d",&a[i]);
    FOR(i,1,n/2) it.update(a[i],-1);
    FOR(i,n/2+1,n) it.update(a[i]-1,1); 
}
void process(void) {
    if (it.getmin()>=0) {
        printf("%d",n/2);
        return;
    }
    FORD(i,n/2-1,1) {
        it.update(a[2*i+1]-1,-1);
        it.update(a[2*i+2]-1,-1);
        it.update(a[i+1],1);
        it.update(a[i+1]-1,1);
        if (it.getmin()>=0) {
            printf("%d",i);
            return;
        }
    }
    printf("-1");
}
int main(void) {
    init();
    process();
    return 0;
}