제출 #1282258

#제출 시각아이디문제언어결과실행 시간메모리
1282258miniobFancy Fence (CEOI20_fancyfence)C++20
30 / 100
99 ms3592 KiB
#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 << x.second << " " << x.first << " " << wys << endl;
	            wyn += wyndla(ilesze, x.first);
	            wyn -= wyndla(ilesze, wys);
	            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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...