Submission #960059

#	Time	Username	Problem	Language	Result	Execution time	Memory
960059		mickytanawin	Group Photo (JOI21_ho_t3)	C++17	100 / 100	4993 ms	72084 KiB

Main

// Tanawin Thongbai

#include <bits/extc++.h>
using namespace std;


class Segm_Elem {
public:
    bool is_real, is_added;
    int sum, unreal, cnt;

    Segm_Elem() {
        is_real = false;
        is_added = false;
        sum = 0;
        unreal = 0;
        cnt = 0;
    }

    Segm_Elem(int sum, int unreal, int cnt, bool is_real) {
        this -> is_real = is_real;
        this -> is_added = true;
        this -> sum = sum;
        this -> unreal = unreal;
        this -> cnt = cnt;
    }
};


const int N = 5000;

int orig[N + 1], indices[N + 1], dp_L[N + 1][N + 1], dp[N + 1];


Segm_Elem segm_merge(const Segm_Elem &a, const Segm_Elem &b) {
    if(!a.is_added) {
        return b;
    }
    if(!b.is_added) {
        return a;
    }
    if(!a.is_real) {
        if(b.is_real) {
            return Segm_Elem(b.sum, a.unreal + b.unreal, b.cnt, true);
        }
        return Segm_Elem(0, a.unreal + b.unreal, 0, false);
    }
    return Segm_Elem(a.sum + b.sum + a.cnt * b.unreal, a.unreal + b.unreal, a.cnt + b.cnt, true);
}


void segm_update(Segm_Elem *const &segm, const int &clogn, int index, Segm_Elem tr) {
    index += (1 << clogn);
    segm[index] = tr;
    for(int i = index / 2; i >= 1; i /= 2) {
        segm[i] = segm_merge(segm[i * 2], segm[i * 2 + 1]);
    }
}


Segm_Elem segm_query(Segm_Elem *const &segm, const int &clogn, int st, int ed) {
    int l = st + (1 << clogn);
    int r = ed + (1 << clogn);
    queue<Segm_Elem> l_part = queue<Segm_Elem>();
    stack<Segm_Elem> r_part = stack<Segm_Elem>();
    while(l <= r) {
        if(l % 2 == 1) {
            l_part.push(segm[l++]);
        }
        if(r % 2 == 0) {
            r_part.push(segm[r--]);
        }
        l /= 2;
        r /= 2;
    }
    bool first_time = true;
    Segm_Elem ans;
    while(!l_part.empty()) {
        Segm_Elem s = l_part.front();
        l_part.pop();
        if(first_time) {
            first_time = false;
            ans = s;
        } else {
            ans = segm_merge(ans, s);
        }
    }
    while(!r_part.empty()) {
        Segm_Elem s = r_part.top();
        r_part.pop();
        if(first_time) {
            first_time = false;
            ans = s;
        } else {
            ans = segm_merge(ans, s);
        }
    }
    return ans;
}


void fenw_update(int *const fenw, const int &n, int i, int x) {
    for(; i <= n; i += i & -i) {
        fenw[i] += x;
    }
}


int fenw_query(int *const fenw, const int &n, int i) {
    int ans = 0;
    for(; i >= 1; i -= i & -i) {
        ans += fenw[i];
    }
    return ans;
}


int main() {
    int n_elem;
    scanf("%d", &n_elem);
    for(int i = 1; i <= n_elem; ++i) {
        scanf("%d", &orig[i]);
        indices[orig[i]] = i;
    }
    for(int i = 1; i <= n_elem - 1; ++i) {
        dp_L[i][i] = 0;
        int *fenw = new int[n_elem + 1]{};
        int k = 1e9;
        for(int j = i + 1; j <= n_elem; ++j) {
            fenw_update(fenw, n_elem, n_elem - indices[j - 1] + 1, 1);
            int mv = 0;
            if(k > indices[j - 1]) {
                k = indices[j - 1];
            }
            if(k != 1e9 && k < indices[j]) {
                mv = fenw_query(fenw, n_elem, n_elem - k + 1) - fenw_query(fenw, n_elem, n_elem - indices[j]);
            }
            dp_L[i][j] = mv + dp_L[i][j - 1];
        }
        delete[] fenw;
    }
    int clogn = (int)ceil(log2(n_elem));
    Segm_Elem *segm = new Segm_Elem[1 << (clogn + 1)]{};
    for(int i = 1; i <= n_elem; ++i) {
        deque<int> deq = deque<int>();
        for(int j = 1; j <= n_elem; ++j) {
            if(i >= orig[n_elem - j + 1]) {
                segm_update(segm, clogn, j - 1, Segm_Elem(0, 1, 0, false));
            }
            if(orig[j] > i) {
                continue;
            }
            if(deq.empty() || orig[deq.back()] < orig[j]) {
                deq.push_back(j);
            }
        }
        int mn = 1e9;
        for(int j = 0; j <= i - 1; ++j) {
            while(!deq.empty() && orig[deq.front()] <= j) {
                deq.pop_front();
            }
            if(j > 0) {
                segm_update(segm, clogn, n_elem - indices[j], Segm_Elem(0, 0, 1, true));
            }
            int mv = 0;
            if(j > 0 && !deq.empty()) {
                int k = deq.front();
                Segm_Elem ans = segm_query(segm, clogn, 0, n_elem - k);
                int x = ans.sum;
                mv = x;
            }
            mn = min(mn, dp[j] + dp_L[j + 1][i] + mv);
        }
        dp[i] = mn;
        for(int j = 1; j <= n_elem; ++j) {
            if(i >= orig[n_elem - j + 1]) {
                segm_update(segm, clogn, j - 1, Segm_Elem());
            }
        }
    }
    printf("%d\n", dp[n_elem]);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |     scanf("%d", &n_elem);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d", &orig[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36