Submission #529580

#	Time	Username	Problem	Language	Result	Execution time	Memory
529580		syl123456	Group Photo (JOI21_ho_t3)	C++17	64 / 100	5050 ms	3928 KiB

Main

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
    if (_sp)
        cout << ' ';
    cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
    if (_sp)
        cout << ' ';
    cout << i;
    DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
    i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << " :";
    for (T _i : j)
        i << ' ' << _i;
    i << '}';
}

typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;

const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

struct seg {
    int l, r, v;
    seg *ch[2]{};
    seg(int _l, int _r) : l(_l), r(_r), v(0) {
        if (l < r - 1)
            ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
    }
    seg(seg *i) : l(i->l), r(i->r), v(i->v), ch{i->ch[0], i->ch[1]} {}
    seg* modify(int i) {
        seg *cpy = new seg(this);
        ++cpy->v;
        if (l == r - 1)
            return cpy;
        int x = i >= l + r >> 1;
        cpy->ch[x] = cpy->ch[x]->modify(i);
        return cpy;
    }
    int query(int _l, int _r) {
        if (_l <= l && r <= _r)
            return v;
        int res = 0;
        if (_l < l + r >> 1)
            res += ch[0]->query(_l, _r);
        if (l + r >> 1 < _r)
            res += ch[1]->query(_l, _r);
        return res;
    }
};

vector<seg*> rts;

int query(int l, int r, int vl, int vr) {
    //0-base[l,r), 0-base[vl, vr)
    if (l == r || vl == vr)
        return 0;
    return rts[r]->query(vl, vr) - rts[l]->query(vl, vr);
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    rts.push_back(new seg(0, n));
    int pos[n];
    for (int i = 0, x; i < n; ++i)
        cin >> x, pos[--x] = i, rts.push_back(rts.back()->modify(x));
    int dp[n + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= n; ++i) {
        dp[i] = inf;
        int tmp = 0, mn = n - i;
        for (int j = 1; j <= i; ++j) {
            int x = mn + j - 1, y = pos[x];
            tmp -= query(y + 1, n, mn, x);
            tmp += query(0, y, x + 1, n);
            tmp += query(0, y, mn, x);
            dp[i] = min(dp[i], dp[i - j] + tmp);
        }
    }
    cout << dp[n];
}
/*
x+1 x+2 x/
x+1 x x+2
x+2 x+1 x

1 [N-1]

2 1 [N-2]

3 2 1 [N-3]

f(n) = min{
    k,k-1,..,1, [n-k]
    f(n-k) + <last n-k><first k> + <first i-1><i (<=k)>
} 1 <= k <= n



*/

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
   21 | }
      | ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
   28 | }
      | ^
Main.cpp: In constructor 'seg::seg(int, int)':
Main.cpp:42:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                ~~^~~
Main.cpp:42:63: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                                             ~~^~~
Main.cpp: In member function 'seg* seg::modify(int)':
Main.cpp:50:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int x = i >= l + r >> 1;
      |                      ~~^~~
Main.cpp: In member function 'int seg::query(int, int)':
Main.cpp:58:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         if (_l < l + r >> 1)
      |                  ~~^~~
Main.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         if (l + r >> 1 < _r)
      |             ~~^~~

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