# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531566 | amunduzbaev | Group Photo (JOI21_ho_t3) | C++17 | 817 ms | 509340 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 5005;
int dp[N], a[N], pos[N];
int inv[N][N], is[N][N];
int pref[N][N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n;i++) cin>>a[i], a[i]--, pos[a[i]] = i;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
is[i][j] = (pos[i] < pos[j]);
if(i && j) pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
else if(i) pref[i][j] = pref[i-1][j];
else if(j) pref[i][j] = pref[i][j-1];
pref[i][j] += is[i][j];
}
}
auto get = [&](int i, int x, int j, int y){
if(i < x) swap(i, x);
if(j < y) swap(j, y);
return pref[i][j] - (y ? pref[i][y-1] : 0) - (x ? pref[x-1][j] : 0) + (x && y ? pref[x-1][y-1] : 0);
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |