Submission #900687

#	Time	Username	Problem	Language	Result	Execution time	Memory
900687		HorizonWest	Group Photo (JOI21_ho_t3)	C++17	100 / 100	492 ms	196708 KiB

Main

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

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

struct ABI
{
    vector <int> tree; 

    void update(int i, int v)
    {
        for(i; i < (int) tree.size(); i += (i & -i))
            tree[i] += v; 
    }

    int sum(int i)
    {   
        int ans = 0; 
        for(i; i > 0; i-= (i & -i))
            ans += tree[i]; 
        return ans; 
    }

    int query(int l, int r)
    {
        if(l <= 1) return sum(r); 
        else return sum(r) - sum(l-1); 
    }

    ABI(int n)
    {
        tree.assign(n + 2, 0); 
    }
};  

void solve()
{
    int n; cin >> n; 
    vector <vector<int>> C(n+1, vector <int> (n+1, 0)); 
    vector <int> v(n), mp(n+1), dp(n+1, Inf); 
    for(auto& u : v) cin >> u; 
    _for(i, n) mp[v[i]] = i + 1; 

    for(int i = 1; i <= n; i++) // Costo para invertir los elementos entre [i, j]
    {
        ABI St(n); 
        for(int j = i; j <= n; j++)
        { 
            if(j != i) C[i][j] = C[i][j-1] + St.query(1, mp[j]); 
            St.update(mp[j], 1); //cerr << mp[j] << " " << St.query(1, mp[j]) << endl; 
        }
    }

    /*_for(i, n)
    { 
        _for(j, n) cerr << C[i+1][j+1] << " ";
        cerr << endl;
    } */

    ABI St1(n); dp[0] = 0; 
    for(int i = 0; i < n; i++)
    {
        int cost = dp[i]; 
        //ABI St2(n); 
        for(int j = 1; i + j <= n; j++)
        {
            int x = mp[i+j] + St1.query(mp[i+j], n); // + St2.query(mp[i+j], n)
            cost += (x - (i + j)); 

            //cout << j << " " << mp[i+j] << " " <<  St1.query(mp[i+j], n) << " " << St2.query(mp[i+j], n)  << " " << (x - (i + j))  << " " << C[i+1][i+j] << endl; 
            //cerr <<  cost <<endl;
            
            dp[i+j] = min(dp[i+j], C[i+1][i+j] + cost); 
            
           // St2.update(mp[j], 1); 
        }
        
        //cerr << dp[n] << endl; 
        St1.update(mp[i+1], 1); //break;
    }

    cout << dp[n] << endl; 
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void ABI::update(long long int, long long int)':
Main.cpp:40:13: warning: statement has no effect [-Wunused-value]
   40 |         for(i; i < (int) tree.size(); i += (i & -i))
      |             ^
Main.cpp: In member function 'long long int ABI::sum(long long int)':
Main.cpp:47:13: warning: statement has no effect [-Wunused-value]
   47 |         for(i; i > 0; i-= (i & -i))
      |             ^

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