Submission #959457

#	Time	Username	Problem	Language	Result	Execution time	Memory
959457		mickytanawin	Group Photo (JOI21_ho_t3)	C++17	0 / 100	1 ms	440 KiB

Main

// Tanawin Thongbai

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


class Fenw_Elem {
public:
    int sum, cnt, i;

    Fenw_Elem() {
        sum = 0;
        cnt = 0;
        i = 0;
    }

    Fenw_Elem(int sum, int cnt, int i) {
        this -> sum = sum;
        this -> cnt = cnt;
        this -> i = i;
    }

    bool operator == (const Fenw_Elem &rhs) const {
        return i == rhs.i && sum == rhs.sum && cnt == rhs.cnt;
    }
};


const int N = 5000;

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


Fenw_Elem fenw_merge(const Fenw_Elem &a, const Fenw_Elem &b) {
    if(b.i == 0) {
        return Fenw_Elem(a.sum + b.sum, a.cnt + b.cnt, a.i);
    }
    return Fenw_Elem(a.sum + b.sum + (a.i - b.i) * a.cnt, a.cnt + b.cnt, b.i == 0? a.i: min(a.i, b.i));
}

Fenw_Elem fenw_query(Fenw_Elem *fenw, const int &n, int i) {
    stack<int> stk = stack<int>();
    for(; i >= 1; i -= i & -i) {
        stk.push(i);
    }
    Fenw_Elem ans = fenw[stk.top()];
    stk.pop();
    while(!stk.empty()) {
        ans = fenw_merge(ans, fenw[stk.top()]);
        stk.pop();
    }
    return ans;
}


void fenw_add(Fenw_Elem *fenw, const int &n, int i, int seq_i) {
    for(; i <= n; i += i & -i) {
        Fenw_Elem f = fenw[i];
        fenw[i] = Fenw_Elem(f.sum + seq_i - f.i, f.cnt + 1, f.i);
    }
}


void fenw_add_blank(Fenw_Elem *fenw, const int &n, int i, int seq_i) {
    for(; i <= n; i += i & -i) {
        Fenw_Elem f = fenw[i];
        fenw[i] = Fenw_Elem(f.sum, f.cnt, seq_i);
    }
}


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; ++i) {
        int cnt = 1;
        for(int j = 1; j <= n_elem; ++j) {
            if(i >= orig[j]) {
                cnts[i][j] = cnt++;
            }
        }
        int cnt_less = 0;
        for(int j = 1; j <= n_elem; ++j) {
            if(orig[j] < i) {
                ++cnt_less;
            }
            less_before[i][j] = cnt_less;
        }
    }
    for(int i = 1; i <= n_elem - 1; ++i) {
        dp_L[i][i] = 0;
        int k = 1e9;
        for(int j = i + 1; j <= n_elem; ++j) {
            int mv = 0;
            if(k > indices[j - 1]) {
                k = indices[j - 1];
            }
            if(k != 1e9 && k < indices[j]) {
                mv = less_before[j][indices[j]] - less_before[j][k] - less_before[i][indices[j]] + less_before[i][k] + 1;
            }
            dp_L[i][j] = mv + dp_L[i][j - 1];
        }
    }
    for(int i = 1; i <= n_elem; ++i) {
        Fenw_Elem *fenw = new Fenw_Elem[n_elem + 1]{};
        deque<int> deq = deque<int>();
        for(int j = 1; j <= n_elem; ++j) {
            if(cnts[i][n_elem - j + 1] > 0) {
                fenw_add_blank(fenw, n_elem, j, cnts[i][n_elem - j + 1]);
            }
            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) {
                fenw_add(fenw, n_elem, n_elem - indices[j] + 1, cnts[i][indices[j]]);
            }
            int mv = 0;
            if(j > 0 && !deq.empty()) {
                int k = deq.front();
                Fenw_Elem ans = fenw_query(fenw, n_elem, n_elem - k + 1);
                mv = ans.sum == 0? 0: ans.sum - ans.cnt + 1;
            }
            mn = min(mn, dp[j] + dp_L[j + 1][i] + mv);
        }
        dp[i] = mn;
        delete[] fenw;
    }
    printf("%d\n", dp[n_elem]);

    return 0;
}

Compilation message (stderr)

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

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