이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
const ll mxN=5e5+5;
const ll mod=1e9+7;
ll pw[mxN];
struct segtree{
vll tree, lazy;
ll treelen;
void init(ll siz){
treelen=siz+1;
while(__builtin_popcount(treelen)!=1){
treelen++;
}
tree.resize(2*treelen);
lazy.resize(2*treelen);
}
void push(ll idx, ll low, ll high){
if(low!=high){
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
}
}
void check(ll idx, ll low, ll high){
tree[idx]+=lazy[idx];
push(idx, low, high);
lazy[idx]=0;
}
void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
check(idx, low, high);
if(low>=qlow && high<=qhigh){
lazy[idx]+=val;
check(idx, low, high);
return;
}
if(low>qhigh || high<qlow){
return;
}
ll mid=(low+high)/2;
update1(2*idx, low, mid, qlow, qhigh, val);
update1(2*idx+1, mid+1, high, qlow, qhigh, val);
tree[idx]=max(tree[2*idx], tree[2*idx+1]);
}
ll getmax1(ll idx, ll low, ll high, ll qlow, ll qhigh){
check(idx, low, high);
if(low>=qlow && high<=qhigh){
return tree[idx];
}
if(low>qhigh || high<qlow){
return 0LL;
}
ll mid=(low+high)/2;
return max(getmax1(2*idx, low, mid, qlow, qhigh),
getmax1(2*idx+1, mid+1, high, qlow, qhigh));
}
void update(ll qlow, ll qhigh, ll val){
update1(1, 0, treelen-1, qlow, qhigh, val);
}
ll getmax(ll qlow, ll qhigh){
return getmax1(1, 0, treelen-1, qlow, qhigh);
}
ll bs(ll idx, ll low, ll high, ll val){
check(idx, low, high);
if(low==high){
return low;
}
ll mid=(low+high)/2;
check(2*idx, low, mid);
if(tree[2*idx]>=val){
return bs(2*idx, low, mid, val);
}
else{
return bs(2*idx+1, mid+1, high, val);
}
}
};
void solve(){
ll n;
cin>>n;
vector<pll> a(n);
for(auto &[x, y]:a){
cin>>x;
}
for(auto &[x, y]:a){
cin>>y;
}
for(auto &[x, y]:a){
if(x>y){
swap(x, y);
}
}
vll h;
for(auto &[x, y]:a){
h.pb(x);
h.pb(y);
}
sort(h.begin(), h.end());
h.erase(unique(h.begin(), h.end()), h.end());
vll pre(n+1);
vll suf(n+2);
vll val(n);
ll ans=0;
ll pr=0;
ll sum=0;
ll tep=0;
for(auto &cur:h){
pre[0]=1;
for(ll i=0;i<n;i++){
val[i]=0;
if(a[i].F<cur){
val[i]++;
}
if(a[i].S<cur){
val[i]++;
}
}
pre[0]=1;
for(ll i=0;i<n;i++){
pre[i+1]=pre[i]*val[i];
pre[i+1]%=mod;
}
suf[n+1]=1;
for(ll i=n-1;i>=0;i--){
suf[i+1]=suf[i+2]*val[i];
suf[i+1]%=mod;
}
sum=0;
for(ll i=0;i<n;i++){
tep=val[i];
tep*=pw[i]-pre[i]+mod;
tep%=mod;
tep*=pw[n-i-1]-suf[i+2]+mod;
tep%=mod;
sum+=tep;
sum%=mod;
}
ans+=sum*(cur-pr);
ans%=mod;
pr=cur;
}
cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
pw[0]=1;
for(ll i=1;i<mxN;i++){
pw[i]=pw[i-1]*2;
pw[i]%=mod;
}
solve();
return 0;
}
# | 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... |