Submission #375206

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375206	2021-03-09T04:26:27 Z	IldarKA	Po (COCI21_po)	C++14	70 / 70	86 ms	11144 KB

Main

#include <bits/stdc++.h>

using namespace std;
int a[100001], n, cnt, p[100001], sz[100001], mn[100001];
long long ans;
bool used[100010];
unordered_map < int, vector < int > > m;
vector < int > v;
int f_l(int x){
    if(p[x] == x){
        return x;
    }
    return p[x] = f_l(p[x]);
}
void u_s(int a, int b){
    a = f_l(a);
    b = f_l(b);
    if(a == b){
        return;
    }
    if(mn[a] != mn[b]){
        cnt++;
    }
    if(sz[a] < sz[b]){
        swap(a, b);
    }
    p[b] = a;
    sz[a] += sz[b];
    mn[a] = min(mn[a], mn[b]);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        m[a[i]].push_back(i);
        v.push_back(a[i]);
        mn[i] = a[i];
        p[i] = i;
        sz[i] = 1;
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for(int i = (int)v.size() - 1; i >= 0; i--){
        cnt = 0;
        if(v[i] == 0) continue;
        for(int j = 0; j < m[v[i]].size(); j++){
            int pos = m[v[i]][j];
            used[pos] = 1;
            if(used[pos - 1] && used[pos + 1]){
                int r = cnt;
                u_s(pos, pos - 1);
                u_s(pos, pos + 1);
                cnt -= (cnt != r);
            }
            else if(!used[pos - 1] && !used[pos + 1]){
                cnt++;
            }
            else if(used[pos - 1]){
                u_s(pos, pos - 1);
            }
            else if(used[pos + 1]){
                u_s(pos, pos + 1);
            }
        }
        ans += cnt;
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0; j < m[v[i]].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	15 ms	1768 KB	Output is correct
5	Correct	24 ms	2404 KB	Output is correct
6	Correct	86 ms	6768 KB	Output is correct
7	Correct	68 ms	11144 KB	Output is correct