Submission #959620

#	Time	Username	Problem	Language	Result	Execution time	Memory
959620		mickytanawin	Group Photo (JOI21_ho_t3)	C++17	0 / 100	2 ms	6584 KiB

Main

// Tanawin Thongbai

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


class Segm_Elem {
public:
    bool is_real;
    short st, ed;
    int sum, unreal;

    Segm_Elem() {
        is_real = false;
        st = 0;
        ed = 0;
        sum = 0;
        unreal = 0;
    }

    Segm_Elem(int sum, int unreal, bool is_real, short st, short ed) {
        this -> is_real = is_real;
        this -> st = st;
        this -> ed = ed;
        this -> sum = sum;
        this -> unreal = unreal;
    }
};


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];


Segm_Elem segm_merge(const Segm_Elem &a, const Segm_Elem &b) {
    if(a.st == 0 && a.ed == 0) {
        return b;
    }
    if(b.st == 0 && b.ed == 0) {
        return a;
    }
    if(!a.is_real) {
        if(b.is_real) {
            return Segm_Elem(b.sum, a.unreal + a.ed - b.st, true, a.st, b.ed);
        }
        return Segm_Elem(0, a.unreal + b.unreal + a.ed - b.st, false, a.st, b.ed);
    }
    return Segm_Elem(a.sum + b.sum + b.unreal + a.ed - b.st, a.unreal, true, a.st, b.ed);
}


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;
}


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];
        }
    }
    int clogn = (int)ceil(log2(n_elem));
    for(int i = 1; i <= n_elem; ++i) {
        Segm_Elem *segm = new Segm_Elem[1 << (clogn + 1)]{};
        deque<int> deq = deque<int>();
        for(int j = 1; j <= n_elem; ++j) {
            if(cnts[i][n_elem - j + 1] > 0) {
                segm_update(segm, clogn, j - 1, Segm_Elem(0, 0, false, cnts[i][n_elem - j + 1], 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) {
                segm_update(segm, clogn, n_elem - indices[j], Segm_Elem(0, 0, true, cnts[i][indices[j]], cnts[i][indices[j]]));
            }
            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;
        delete[] segm;
    }
    printf("%d\n", dp[n_elem]);

    return 0;
}

Compilation message (stderr)

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

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