답안 #964799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964799	2024-04-17T15:04:16 Z	efedmrlr	Rope (JOI17_rope)	C++17	0 / 100	1 ms	460 KB

rope

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<int> a;
vector<int> cnt;
vector<vector<int> > pr1, pr2;
set<array<int,2> > st1, st2;

void upd(int ind, int val, bool f) {
    if(!f) {
        auto tmp = st1.lower_bound({cnt[ind], ind});
        assert(tmp != st1.end());
        st1.erase(tmp);
        cnt[ind] += val;
        st1.insert({cnt[ind], ind});

    }
    else {
        auto tmp = st2.lower_bound({cnt[ind], ind});
        assert(tmp != st2.end());
        st2.erase(tmp);
        cnt[ind] += val;
        st2.insert({cnt[ind], ind});
        
    }
}


inline void solve() {
    cin>>n>>m;
    a.resize(n + 5);
    cnt.assign(m + 5, 0);
    pr1.assign(m + 5, vector<int>());
    pr2.assign(m + 5, vector<int>());
    
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    } 
    for(int i = 1; i<=n; i++) {
        cnt[a[i]]++;
    }
    for(int i = 1; i<n; i+=2) {
        if(a[i] == a[i + 1]) continue;
        pr1[a[i]].pb(a[i + 1]);
        pr1[a[i + 1]].pb(a[i]);
    }
    for(int i = 2; i<n; i+=2) {
        if(a[i] == a[i + 1]) continue; 
        pr2[a[i]].pb(a[i + 1]);
        pr2[a[i + 1]].pb(a[i]);
        
    }
    for(int i = 1; i<=m; i++) {
        st1.insert({cnt[i], i});
        st2.insert({cnt[i], i});
    }
    vector<int> res(m + 1, INF);
    for(int i = 1; i<=m; i++) {
        res[i] = n - cnt[i];
    }
    
    for(int i = 1; i<=m; i++) {
        // Case 1
        for(auto c : pr1[i]) {
            upd(c, -1, 0);
        }
        st1.erase({cnt[i], i});
        res[i] = min(res[i], n - (cnt[i] + (*prev(st1.end()))[0]));
        st1.insert({cnt[i], i});
        for(auto c : pr1[i]) {
            upd(c, 1, 0);
        }

        // Case 2
        for(auto c : pr2[i]) {
            upd(c, -1, 1);
        }
        st2.erase({cnt[i], i});
        res[i] = min(res[i], n - (cnt[i] + (*prev(st2.end()))[0]));
        st2.insert({cnt[i], i});
        for(auto c : pr2[i]) {
            upd(c, 1, 1);
        }
    }
    for(int i = 1; i<=m; i++) {
        cout << res[i] << "\n";
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	420 KB	Output is correct
7	Correct	1 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	420 KB	Output is correct
7	Correct	1 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	420 KB	Output is correct
7	Correct	1 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	420 KB	Output is correct
7	Correct	1 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	420 KB	Output is correct
7	Correct	1 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	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	1 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Runtime error	1 ms	348 KB	Execution killed with signal 11
23	Halted	0 ms	0 KB	-

답안 #964799

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
0 / 15.0

Subtask #2
0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0