Submission #670486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670486	2022-12-09T08:55:39 Z	Mahdi	Rope (JOI17_rope)	C++17	0 / 100	29 ms	47992 KB

rope

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1e6+5;
int n, m, c[N], cnt[N], ans[N];
vector<int>v[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>c[i];
        v[c[i]].push_back(i);
        ++cnt[c[i]];
    }
    set<pii>s;
    for(int i=1;i<=m;++i)
        s.insert({cnt[i], i});
    for(int i=1;i<=m;++i){
        s.erase({cnt[i], i});
        vector<int>w;
        for(int u: v[i]){
            int z=u+((u&1) ? -1 : 1);
            if(z>0 && z<=n && c[z]!=i){
                z=c[z];
                s.erase({cnt[z], z});
                w.push_back(z);
                --cnt[z];
                s.insert({cnt[z], z});
            }
        }
        auto it=s.end();
        --it;
        ans[i]=cnt[i]+it->F;
        for(int u: w){
            s.erase({cnt[u], u});
            ++cnt[u];
            s.insert({cnt[u], u});
        }
        w.clear();
        for(int u: v[i]){
            int z=u+((u&1) ? 1 : -1);
            if(z>0 && z<=n && c[z]!=i){
                z=c[z];
                s.erase({cnt[z], z});
                w.push_back(z);
                --cnt[z];
                s.insert({cnt[z], z});
            }
        }
        it=s.end();
        --it;
        ans[i]=max(ans[i], cnt[i]+it->F);
        for(int u: w){
            s.erase({cnt[u], u});
            ++cnt[u];
            s.insert({cnt[u], u});
        }
        s.insert({cnt[i], i});
    }
    for(int i=1;i<=m;++i)
        cout<<n-ans[i]<<'\n';
}

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23816 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	12 ms	23812 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23736 KB	Output is correct
8	Correct	13 ms	23788 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	12 ms	23772 KB	Output is correct
11	Correct	11 ms	23712 KB	Output is correct
12	Correct	12 ms	23808 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23808 KB	Output is correct
17	Correct	14 ms	23764 KB	Output is correct
18	Correct	12 ms	23812 KB	Output is correct
19	Correct	13 ms	23800 KB	Output is correct
20	Correct	12 ms	23736 KB	Output is correct
21	Correct	12 ms	23812 KB	Output is correct
22	Runtime error	29 ms	47992 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23816 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	12 ms	23812 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23736 KB	Output is correct
8	Correct	13 ms	23788 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	12 ms	23772 KB	Output is correct
11	Correct	11 ms	23712 KB	Output is correct
12	Correct	12 ms	23808 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23808 KB	Output is correct
17	Correct	14 ms	23764 KB	Output is correct
18	Correct	12 ms	23812 KB	Output is correct
19	Correct	13 ms	23800 KB	Output is correct
20	Correct	12 ms	23736 KB	Output is correct
21	Correct	12 ms	23812 KB	Output is correct
22	Runtime error	29 ms	47992 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23816 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	12 ms	23812 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23736 KB	Output is correct
8	Correct	13 ms	23788 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	12 ms	23772 KB	Output is correct
11	Correct	11 ms	23712 KB	Output is correct
12	Correct	12 ms	23808 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23808 KB	Output is correct
17	Correct	14 ms	23764 KB	Output is correct
18	Correct	12 ms	23812 KB	Output is correct
19	Correct	13 ms	23800 KB	Output is correct
20	Correct	12 ms	23736 KB	Output is correct
21	Correct	12 ms	23812 KB	Output is correct
22	Runtime error	29 ms	47992 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23816 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	12 ms	23812 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23736 KB	Output is correct
8	Correct	13 ms	23788 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	12 ms	23772 KB	Output is correct
11	Correct	11 ms	23712 KB	Output is correct
12	Correct	12 ms	23808 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23808 KB	Output is correct
17	Correct	14 ms	23764 KB	Output is correct
18	Correct	12 ms	23812 KB	Output is correct
19	Correct	13 ms	23800 KB	Output is correct
20	Correct	12 ms	23736 KB	Output is correct
21	Correct	12 ms	23812 KB	Output is correct
22	Runtime error	29 ms	47992 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct
3	Correct	12 ms	23816 KB	Output is correct
4	Correct	13 ms	23756 KB	Output is correct
5	Correct	12 ms	23812 KB	Output is correct
6	Correct	12 ms	23764 KB	Output is correct
7	Correct	12 ms	23736 KB	Output is correct
8	Correct	13 ms	23788 KB	Output is correct
9	Correct	13 ms	23764 KB	Output is correct
10	Correct	12 ms	23772 KB	Output is correct
11	Correct	11 ms	23712 KB	Output is correct
12	Correct	12 ms	23808 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	12 ms	23764 KB	Output is correct
16	Correct	12 ms	23808 KB	Output is correct
17	Correct	14 ms	23764 KB	Output is correct
18	Correct	12 ms	23812 KB	Output is correct
19	Correct	13 ms	23800 KB	Output is correct
20	Correct	12 ms	23736 KB	Output is correct
21	Correct	12 ms	23812 KB	Output is correct
22	Runtime error	29 ms	47992 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-