이 제출은 이전 버전의 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=vll(2*treelen, 1);
}
void build(ll idx, ll low, ll high, vll &a){
if(low==high){
if(low<a.size()) tree[idx]=a[low];
else tree[idx]=0;
return;
}
ll mid=(low+high)/2;
build(2*idx, low, mid, a);
build(2*idx+1, mid+1, high, a);
tree[idx]=tree[2*idx]+tree[2*idx+1];
tree[idx]%=mod;
}
void push(ll idx, ll low, ll high){
if(low!=high){
lazy[2*idx]*=lazy[idx];
lazy[2*idx]%=mod;
lazy[2*idx+1]*=lazy[idx];
lazy[2*idx+1]%=mod;
}
}
void check(ll idx, ll low, ll high){
tree[idx]*=lazy[idx];
tree[idx]%=mod;
push(idx, low, high);
lazy[idx]=1;
}
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;
lazy[idx]%=mod;
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]=tree[2*idx]+tree[2*idx+1];
tree[idx]%=mod;
}
ll getsum1(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 (getsum1(2*idx, low, mid, qlow, qhigh)+
getsum1(2*idx+1, mid+1, high, qlow, qhigh))%mod;
}
void update(ll qlow, ll qhigh, ll val){
update1(1, 0, treelen-1, qlow, qhigh, val);
}
ll getsum(ll qlow, ll qhigh){
return getsum1(1, 0, treelen-1, qlow, qhigh);
}
};
segtree seg;
vll con;
ll id(ll tar){
return lower_bound(con.begin(), con.end(), tar)-con.begin();
}
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);
}
}
for(auto &[x, y]:a){
con.pb(x);
con.pb(y);
}
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
ll siz=con.size();
vll bas(siz);
bas[0]=con[0];
for(ll i=1;i<siz;i++){
bas[i]=con[i]-con[i-1];
}
seg.init(siz);
seg.build(1, 0, seg.treelen-1, bas);
ll ans=0;
vll cnt(siz);
for(auto &[x, y]:a){
cnt[id(x)]++;
cnt[id(y)]++;
}
ll pre=0;
for(ll i=0;i<siz;i++){
ans+=((pre*pw[n-1])%mod)*bas[i];
ans%=mod;
pre+=cnt[i];
}
for(ll i=0;i<n;i++){
ll id1=id(a[i].F);
ll id2=id(a[i].S);
seg.update(0, id1, 0);
if(id2+1<siz) seg.update(id2+1, siz-1, 2);
ans-=seg.getsum(0, siz-1)*pw[n-i-1];
ans%=mod;
if(ans<0) ans+=mod;
}
seg.init(siz);
seg.build(1, 0, seg.treelen-1, bas);
for(ll i=n-1;i>=0;i--){
ll id1=id(a[i].F);
ll id2=id(a[i].S);
seg.update(0, id1, 0);
if(id2+1<siz) seg.update(id2+1, siz-1, 2);
ans-=seg.getsum(0, siz-1)*pw[i];
ans%=mod;
if(ans<0) ans+=mod;
}
ans+=seg.getsum(0, siz-1)*n;
ans%=mod;
cout<<ans<<'\n';
/*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;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In member function 'void segtree::build(ll, ll, ll, std::vector<long long int>&)':
Main.cpp:33:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(low<a.size()) tree[idx]=a[low];
| ~~~^~~~~~~~~
# | 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... |