제출 #375181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375181		IldarKA	Po (COCI21_po)	C++14	20 / 70	71 ms	12040 KiB

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;
        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--;
            }
            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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 20 / 70