AtCoder Grand Contest 005

Submission #1585849

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second
namespace taolu
{
	const int N=201000;
	typedef long long ll;
	typedef std::pair<int,int> pii;
	struct disjoint_set_union
	{
		int q[N],w[N];
		void init(int n){for(int i=1;i<=n;i++)q[i]=i,w[i]=1;}
		int ask(int p){return p!=q[p]?q[p]=ask(q[p]):p;}
		void link(int u,int v){w[ask(v)]+=w[ask(u)];q[ask(u)]=ask(v);}
		bool uni(int u,int v){return ask(u)==ask(v);}
		int query(int p){return w[ask(p)];}
	}d;
	bool ex[N];
	pii s[N];
	int n;
	ll ans;
	void initialize()
	{
		scanf("%d",&n);
		for(int i=1,x;i<=n;i++)
			scanf("%d",&x),s[i]=pii(x,i);
		std::sort(s+1,s+n+1);
	}
	void solve()
	{
		initialize();
		ans=0;
		d.init(n);
		for(int i=n;i;i--)
		{
			int p=s[i].y,x=0,y=0;
			if(ex[p-1])x=d.query(p-1),d.link(p,p-1);
			if(ex[p+1])y=d.query(p+1),d.link(p,p+1);
			ans+=(ll)(x+1)*(y+1)*s[i].x;
			ex[p]=1;
		}
		printf("%lld\n",ans);
	}
}
int main()
{
	taolu::solve();
	return 0;
}

Submission

Task問題 B - Minimum Sum
User nameユーザ名 Demerzel_IV
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 1044 Byte
File nameファイル名
Exec time実行時間 41 ms
Memory usageメモリ使用量 3584 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘void taolu::initialize()’:
./Main.cpp:27:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:29:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x),s[i]=pii(x,i);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2
All 400 / 400 corner0,corner1,corner2,corner3,example0,example1,example2,maxrand0,maxrand1,maxrand2,rand0,rand1,rand2

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
corner0 AC 26 ms 3584 KB
corner1 AC 25 ms 3584 KB
corner2 AC 1 ms 256 KB
corner3 AC 40 ms 3584 KB
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
maxrand0 AC 41 ms 3584 KB
maxrand1 AC 40 ms 3584 KB
maxrand2 AC 40 ms 3584 KB
rand0 AC 1 ms 256 KB
rand1 AC 1 ms 256 KB
rand2 AC 1 ms 256 KB