Submission #1282264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282264		miniob	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	62 ms	3520 KiB

fancyfence

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

long long h[100007];
long long w[100007];

long long wyndla(long long a, long long b)
{
	__int128 aa = (__int128)a * ((__int128)a + (__int128)1) / (__int128)2;
	__int128 bb = (__int128)b * ((__int128)b + (__int128)1) / (__int128)2;
	aa %= (__int128)1000000007;
	bb %= (__int128)1000000007;
	return (((aa % (long long)1000000007) * (bb % (long long)1000000007)) % (long long)1000000007);
}

int main() 
{
    long long n, wyn = 0;
    cin >> n;
    deque<pair<long long, long long>> q;  // wys, szer
    for (long long i = 0; i < n; i++) 
    {
        cin >> h[i];
    }
    for (long long i = 0; i < n; i++) 
    {
        cin >> w[i];
    }
    for (long long i = 0; i <= n; i++)
    {
        if (q.empty())
        {
            q.push_back({h[i], w[i]});
        }
        else 
        {
            long long ilesze = 0;
            while (!q.empty() && (q.back()).first > h[i]) 
            {
                auto x = q.back();
                ilesze += x.second;
                q.pop_back();
                long long wys = 0;
	            if(!q.empty())
	            {
	            	wys = (q.back()).first;
	            }
	            //cout << ilesze << " " << x.first << " " << wys << endl;
	            //cout <<  wyndla(ilesze, x.first) << " " << wyndla(ilesze, wys) << endl;
	            wyn += wyndla(ilesze, x.first);
	            wyn -= wyndla(ilesze, max(wys, h[i]));
	            wyn += 1000000007;
	            wyn %= 1000000007;
            }
            if (q.empty() || (q.back()).first < h[i]) 
            {
            	q.push_back({h[i], w[i] + ilesze});	
            }
            else
            {
            	auto x = q.back();
            	q.pop_back();
            	x.second += w[i] + ilesze;
            	q.push_back(x);
            }
        }
    }
	cout << wyn << endl;
    return 0;
}

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