Submission #1305636


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = 3.141592653589793;

int n;
int a[200000+5],pos[200000+5];

class UnionFind{
    private:
        vector<int> parent,rank,tree_w;
        int tree_num;
    public:
        UnionFind(int size){
            tree_num=size;
            for (int i=0; i<size; i++){
                parent.push_back(i);
                rank.push_back(0);
                tree_w.push_back(1);
            }
        }

        int findset(int x){
            return x==parent[x] ? x : parent[x]=findset(parent[x]);
        }

        void unite(int x,int y){
            x=findset(x);y=findset(y);
            if (x==y) return;
            if (rank[x]>rank[y]) swap(x,y);
            parent[x]=y;
            tree_num-=1;
            tree_w[y]+=tree_w[x];
            if (rank[x]==rank[y]) rank[y]+=1;
        }

        bool same(int x,int y){
            return findset(x)==findset(y);
        }

        int tree_number(){
            return tree_num;
        }

        int tree_weight(int x){
            return tree_w[findset(x)];
        }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    rep(i,n) cin >> a[i];
    rep(i,n) pos[a[i]]=i;
    bool check[n];
    UnionFind uf(n);
    ll ans=0;
    rrep(i,n){
        int l=max(pos[i]-1,0);
        int r=min(pos[i]+1,n-1);
        int lnum=1;
        int rnum=1;
        if (check[l]){
            lnum+=uf.tree_weight(l);
        }
        if (check[r]){
            rnum+=uf.tree_weight(r);
        }
        if (check[l]){
            uf.unite(l,pos[i]);
        }
        if (check[r]){
            uf.unite(r,pos[i]);
        }
        check[pos[i]]=true;
        ans+=i*lnum*rnum;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Minimum Sum
User roto_37
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2476 Byte
Status WA
Exec Time 29 ms
Memory 4576 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
WA × 3
WA × 13
Set Name Test Cases
Sample example0, example1, example2
All corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 WA 23 ms 4576 KB
corner1 WA 23 ms 4576 KB
corner2 WA 1 ms 256 KB
corner3 WA 24 ms 4576 KB
example0 WA 1 ms 256 KB
example1 WA 1 ms 256 KB
example2 WA 1 ms 256 KB
maxrand0 WA 29 ms 4576 KB
maxrand1 WA 29 ms 4576 KB
maxrand2 WA 29 ms 4576 KB
rand0 WA 1 ms 256 KB
rand1 WA 1 ms 256 KB
rand2 WA 1 ms 256 KB