Submission #1305667
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];
a[i]--;
}
rep(i,n) pos[a[i]]=i;
bool check[n]={};
UnionFind uf(n);
ll ans=0;
rrep(i,n-1){
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+1)*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 |
2517 Byte |
Status |
WA |
Exec Time |
29 ms |
Memory |
4576 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 400 |
Status |
|
|
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 |
AC |
1 ms |
256 KB |
corner3 |
WA |
24 ms |
4576 KB |
example0 |
AC |
1 ms |
256 KB |
example1 |
AC |
1 ms |
256 KB |
example2 |
AC |
1 ms |
256 KB |
maxrand0 |
WA |
29 ms |
4576 KB |
maxrand1 |
WA |
29 ms |
4576 KB |
maxrand2 |
WA |
29 ms |
4576 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
1 ms |
256 KB |
rand2 |
AC |
1 ms |
256 KB |