Submission #2237

#	Time	Username	Problem	Language	Result	Execution time	Memory
2237		kriii	지우개 (GA4_eraser)	C++98	100 / 100	40 ms	3232 KiB

eraser

#include <stdio.h>
#include <algorithm>
#define max_a 100100

const long long mod = 1000000007;
int N; long long a[max_a],b[max_a],c[max_a],d;

void add(long long &a, long long p)
{
	a += p;
	if (a >= mod) a -= mod;
}

void in(long long *t, int x, long long p)
{
	for (;x<max_a;x+=x&(-x)) add(t[x],p); 
}

long long out(long long *t, int x)
{
	long long r = 0;
	for (;x;x-=x&(-x)) add(r,t[x]);
	return r;
}

int main()
{
	int i;

	scanf ("%d",&N);
	for (i=0;i<N;i++) scanf ("%lld",&a[i]);
	std::sort(a,a+N);

	for (i=0;i<N;i++){
		in(b,a[i],a[i]);
		in(c,a[i],a[i]*out(b,a[i]-1)%mod);
		add(d,a[i]*out(c,a[i]-1)%mod);
	}

	printf ("%lld",d);

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 26 / 26
• Subtask 6: 28 / 28