Submission #854125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
854125	2023-09-26T07:48:03 Z	LeVanThuc	Group Photo (JOI21_ho_t3)	C++17	100 / 100	3851 ms	143204 KB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef thuc
    freopen("input.INP","r",stdin);
    freopen("output.OUT","w",stdout);
#endif
}
const int N=5e3+10,M=1e9+7;
ll n,a[N],pos[N];
struct PSeg
{
    vector<ll> Head;
    struct Node
    {
        ll l,r,vl;
    };
    ll cnt,n;
    vector<Node> Tree;
    ll make(ll x,ll y,ll z)
    {
        Tree[++cnt].l=x;
        Tree[cnt].r=y;
        Tree[cnt].vl=z;
        return cnt;
    }
    ll build(ll l,ll r)
    {
        if(l==r) return make(0,0,0);
        return make(build(l,(l+r)/2),build((l+r)/2+1,r),0);
    }
    PSeg(ll _n=0)
    {
        n=_n;
        Tree.resize(22*n);
        Head.push_back(build(1,n));
    }
    ll update(ll i,ll l,ll r,ll pos,ll vl)
    {
        if(r<pos||pos<l) return i;
        if(l==r) return make(0,0,vl);
        ll x=update(Tree[i].l,l,(l+r)/2,pos,vl);
        ll y=update(Tree[i].r,(l+r)/2+1,r,pos,vl);
        return make(x,y,Tree[x].vl+Tree[y].vl);
    }
    ll query(ll i,ll l,ll r,ll l1,ll r1)
    {
        if(r1<l||r<l1) return 0;
        if(l1<=l&&r<=r1) return Tree[i].vl;
        return query(Tree[i].l,l,(l+r)/2,l1,r1)+query(Tree[i].r,(l+r)/2+1,r,l1,r1);
    }
    ll query(ll l,ll r,ll l1,ll r1)
    {
        if(l>r) return 0;
        return query(Head[r],1,n,l1,r1)-query(Head[l-1],1,n,l1,r1);
    }
};
ll c[N][N],f[N];
int main()
{
    online();
    cin>>n;
    PSeg S(n);
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        pos[a[i]]=i;
        S.Head.push_back(S.update(S.Head.back(),1,n,a[i],1));
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
        {
            c[i][j]=c[i][j-1];
            c[i][j]+=S.query(1,pos[j]-1,i,n);
            c[i][j]-=S.query(pos[j],n,i,j-1);
            minimize(f[j],f[i-1]+c[i][j]);
        }
    }
    cout<<f[n];
}

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	600 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct

Subtask #3
32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	6 ms	1372 KB	Output is correct
22	Correct	4 ms	1372 KB	Output is correct
23	Correct	5 ms	1372 KB	Output is correct
24	Correct	5 ms	1368 KB	Output is correct
25	Correct	5 ms	1372 KB	Output is correct
26	Correct	5 ms	1372 KB	Output is correct
27	Correct	4 ms	1372 KB	Output is correct
28	Correct	4 ms	1372 KB	Output is correct
29	Correct	5 ms	1372 KB	Output is correct
30	Correct	4 ms	1372 KB	Output is correct

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	6 ms	1372 KB	Output is correct
22	Correct	4 ms	1372 KB	Output is correct
23	Correct	5 ms	1372 KB	Output is correct
24	Correct	5 ms	1368 KB	Output is correct
25	Correct	5 ms	1372 KB	Output is correct
26	Correct	5 ms	1372 KB	Output is correct
27	Correct	4 ms	1372 KB	Output is correct
28	Correct	4 ms	1372 KB	Output is correct
29	Correct	5 ms	1372 KB	Output is correct
30	Correct	4 ms	1372 KB	Output is correct
31	Correct	74 ms	8328 KB	Output is correct
32	Correct	78 ms	8592 KB	Output is correct
33	Correct	75 ms	8388 KB	Output is correct
34	Correct	74 ms	8276 KB	Output is correct
35	Correct	76 ms	8320 KB	Output is correct
36	Correct	74 ms	8272 KB	Output is correct
37	Correct	73 ms	8756 KB	Output is correct
38	Correct	73 ms	8272 KB	Output is correct
39	Correct	75 ms	8272 KB	Output is correct
40	Correct	76 ms	8328 KB	Output is correct

Subtask #5
36.0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	600 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	0 ms	604 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	6 ms	1372 KB	Output is correct
22	Correct	4 ms	1372 KB	Output is correct
23	Correct	5 ms	1372 KB	Output is correct
24	Correct	5 ms	1368 KB	Output is correct
25	Correct	5 ms	1372 KB	Output is correct
26	Correct	5 ms	1372 KB	Output is correct
27	Correct	4 ms	1372 KB	Output is correct
28	Correct	4 ms	1372 KB	Output is correct
29	Correct	5 ms	1372 KB	Output is correct
30	Correct	4 ms	1372 KB	Output is correct
31	Correct	74 ms	8328 KB	Output is correct
32	Correct	78 ms	8592 KB	Output is correct
33	Correct	75 ms	8388 KB	Output is correct
34	Correct	74 ms	8276 KB	Output is correct
35	Correct	76 ms	8320 KB	Output is correct
36	Correct	74 ms	8272 KB	Output is correct
37	Correct	73 ms	8756 KB	Output is correct
38	Correct	73 ms	8272 KB	Output is correct
39	Correct	75 ms	8272 KB	Output is correct
40	Correct	76 ms	8328 KB	Output is correct
41	Correct	3629 ms	142844 KB	Output is correct
42	Correct	3725 ms	142844 KB	Output is correct
43	Correct	3751 ms	142992 KB	Output is correct
44	Correct	3718 ms	142900 KB	Output is correct
45	Correct	3720 ms	142816 KB	Output is correct
46	Correct	3796 ms	142864 KB	Output is correct
47	Correct	3645 ms	142984 KB	Output is correct
48	Correct	3736 ms	142904 KB	Output is correct
49	Correct	3754 ms	142980 KB	Output is correct
50	Correct	3664 ms	142900 KB	Output is correct
51	Correct	3725 ms	143164 KB	Output is correct
52	Correct	3611 ms	143012 KB	Output is correct
53	Correct	3607 ms	142844 KB	Output is correct
54	Correct	3851 ms	142924 KB	Output is correct
55	Correct	3705 ms	143204 KB	Output is correct

Submission #854125

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 32.0 / 32.0

Subtask #4 20.0 / 20.0

Subtask #5 36.0 / 36.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
32.0 / 32.0

Subtask #4
20.0 / 20.0

Subtask #5
36.0 / 36.0