이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn=2e5+69;
const ll mod=1e9+7;
const ll inf=1e18;
int n,a[maxn],b[maxn];
namespace sub2
{
int mu2[maxn];
void sol()
{
mu2[0]=1;
for1(i,1,n) mu2[i]=mu2[i-1]*2%mod;
int res=0;
for1(i,1,n)
{
res+=mu2[n-1]-mu2[i-1]-mu2[n-i]+1;
}
cout << res;
}
}
namespace sub1
{
int x[50],pre[50],suf[50];
void sol()
{
int ans=0;
// for1(mask,6,6)
for1(mask,0,(1<<n)-1)
{
for1(i,1,n)
{
if ((mask>>(i-1))&1) x[i]=a[i];
else x[i]=b[i];
// cerr<< x[i]<<' ';
}
// cerr<< '\n';
for1(i,1,n) pre[i]=max(pre[i-1],x[i]);
for2(i,n,1) suf[i]=max(suf[i+1],x[i]);
for1(i,1,n)
{
// if (pre[i-1]<x[i] || suf[i+1]<x[i]) continue;
// if (min(pre[i],suf[i])-x[i]<0) cerr<< "gg\n";
ans+=min(pre[i],suf[i])-x[i];
ans%=mod;
}
}
cout << ans;
}
}
void sol()
{
cin >> n;
for1(i,1,n) cin >> a[i];
bool is_sub2=1;
for1(i,1,n)
{
cin >> b[i];
if (b[i]<a[i]) swap(a[i],b[i]);
if (a[i]!=1 || b[i]!=2) is_sub2=0;
}
if (is_sub2)
{
sub2::sol();
return;
}
if (n<=20)
{
sub1::sol();
return;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("wall.inp","r",stdin);
// freopen("wall.out","w",stdout);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |