Submission #580227

#	Time	Username	Problem	Language	Result	Execution time	Memory
580227		MODDI	Fancy Fence (CEOI20_fancyfence)	C++14	28 / 100	80 ms	2684 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
const int MOD = 1e9 + 7;
int main(){
	int n;
	cin>>n;
	vl visina, sirina;
	bool all_same = true, sorted = true;
	for(int i = 0; i < n; i++){
		ll a;
		cin>>a;
		visina.pb(a);
		if(i > 0 && visina[i] != visina[i-1]){
			all_same = false;
		}
		if(i > 0 && visina[i] < visina[i-1]){
			sorted = false;
		}
	}
	for(int i = 0; i < n; i++){
		ll a;
		cin>>a;
		sirina.pb(a);
	}
	ll rez = 0, cur = 0, sum = 0;
	if(all_same){
		ll vis = 0, sir = 0;
		for(int i = 0; i < n; i++){
			sir += sirina[i];
			sir %= MOD;
		}
		vis = visina[0];
		vis %= MOD;
		sir %= MOD;
		rez = sir * (sir + 1) / 2;
		rez %= MOD;
		ll rez2 = vis * (vis + 1) / 2;
		rez2 %= MOD;
		cout<<(rez*rez2)%MOD<<endl;
		return 0;
	}
	if(sorted){
		ll rez = 0, ss = 0;
		vl sum;
		sum.resize(n);
		for(int i = n-1; i >=0;i--){
			ss += sirina[i];
			ss %= MOD;
			sum[i] = ss;
			if(sum[i] >= MOD || sum[i] < 0)
				assert(false);
		}
		for(int i = 0; i < n; i++){
			if(i == 0){
				ll sir = sum[i];
				sir %= MOD;
				ll vis = visina[i];
				vis %= MOD;
				ll rez1 = vis * (vis + 1) / 2;
				rez1 %= MOD;
				ll rez2 = sir * (sir + 1) / 2;
				rez2 %= MOD;
				rez += (rez1 * rez2) % MOD;
				rez %= MOD;
			}
			else{
				ll sir = sum[i];
				sir%=MOD;
				ll vis1 = visina[i], vis2 = visina[i-1];
				vis1 %= MOD;
				vis2 %= MOD;
				ll sega = sir *(sir + 1) / 2;
				sega %= MOD;
				ll sega1 = vis1*(vis1+1) / 2;
				sega1%=MOD;
				ll rez1 = (sega * sega1) % MOD;
				ll sega2 = vis2*(vis2 + 1) / 2;
				sega2%= MOD;
				ll rez2 = (sega * sega2) % MOD;
				rez2 %= MOD;
				if(rez1 >= MOD || rez2 >= MOD)
					assert(false);
				ll add = (rez1 - rez2)%MOD;
				if(add >= MOD || add < 0)
					assert(false);
				add %= MOD;
				rez += add;
				rez %= MOD;
			}
		}
		cout<<rez%MOD<<endl;
		return 0;
	}
	for(int i = 0; i < n; i++){
		sum += sirina[i];
		sum %= MOD;
		if(visina[i] == 2)
		{
			cur += sirina[i];
			cur %= MOD;
		}
		else{
			if(cur > 0){
				rez += cur * (cur + 1);
				rez %= MOD;
				cur = 0;
			}
		}
	}
	if(cur > 0){
		rez += cur * (cur + 1);
		rez %= MOD;
	}
	rez += sum * (sum + 1) / 2;
	rez %= MOD;
	cout<<rez<<endl;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27