QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#894004 | #8712. Flooding Wall | sitablechair | 0 | 1ms | 4352kb | C++14 | 3.3kb | 2025-02-11 10:34:52 | 2025-02-11 10:34:53 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=10000,MOD=1e9+7,INV=500000004;
struct SegTree {
ll tr[N*4];
void reset(int id,int l,int r) {
tr[id]=0;
if (l==r) return;
int mid=l+r>>1;
reset(id*2,l,mid);
reset(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u,int x) {
if (l>u || r<u) return;
if (l==r) return void(tr[id]=x);
int mid=l+r>>1;
update(id*2,l,mid,u,x);
update(id*2+1,mid+1,r,u,x);
tr[id]=tr[id*2]*tr[id*2+1]%MOD;
}
ll query(int id,int l,int r,int u,int v) {
if (l>v || r<u) return 1;
if (l>=u && r<=v) return tr[id];
int mid=l+r>>1;
return query(id*2,l,mid,u,v)*query(id*2+1,mid+1,r,u,v)%MOD;
}
} st;
int n,a[N],b[N],c[N],lft[N][2],rgt[N][2];
vector<pair<int,int>> in[N*2];
vector<ll> big;
ll ans=0;
void solve() {
cin >> n;
For(i,1,n) {
cin >> a[i];
big.pb(a[i]);
}
For(i,1,n) {
cin >> b[i];
big.pb(b[i]);
}
sort(all(big));
unq(big);
For(i,1,n) in[lower_bound(all(big),a[i])-big.begin()+1].pb({i,0});
For(i,1,n) in[lower_bound(all(big),b[i])-big.begin()+1].pb({i,1});
For(i,1,n) c[i]=0;
st.reset(1,1,n);
For(i,1,sz(big)) {
for(auto el: in[i-1]) {
c[el.ff]++;
st.update(1,1,n,el.ff,c[el.ff]);
}
for(auto el: in[i]) {
if (el.ff>1) lft[el.ff][el.ss]=st.query(1,1,n,1,el.ff-1);
else lft[el.ff][el.ss]=0;
if (el.ff<n) rgt[el.ff][el.ss]=st.query(1,1,n,el.ff+1,n);
else rgt[el.ff][el.ss]=0;
}
}
For(i,1,n) c[i]=0;
For(i,1,sz(big)) {
for(auto el: in[i-1]) c[el.ff]++;
for(auto el: in[i]) {
ll tmp=1;
ForD(j,el.ff-1,1) {
tmp=tmp*c[j]%MOD;
if (tmp==0) break;
if (a[j]>=big[i]) ans=(ans+big[i-1]*tmp%MOD*lft[j][0]%MOD*rgt[el.ff][el.ss]%MOD*(el.ff-j-1)%MOD)%MOD;
if (b[j]>=big[i]) ans=(ans+big[i-1]*tmp%MOD*lft[j][1]%MOD*rgt[el.ff][el.ss]%MOD*(el.ff-j-1)%MOD)%MOD;
}
tmp=1;
For(j,el.ff+1,n) {
tmp=tmp*c[j]%MOD;
if (tmp==0) break;
if (a[j]>big[i]) ans=(ans+big[i-1]*tmp%MOD*rgt[j][0]%MOD*lft[el.ff][el.ss]%MOD*(j-el.ff-1)%MOD)%MOD;
if (b[j]>big[i]) ans=(ans+big[i-1]*tmp%MOD*rgt[j][1]%MOD*lft[el.ff][el.ss]%MOD*(j-el.ff-1)%MOD)%MOD;
}
}
}
ll tmp=2;
For(i,1,n-1) tmp=tmp*2%MOD;
For(i,1,n) ans=(ans-1LL*a[i]*tmp%MOD)%MOD;
For(i,1,n) ans=(ans-1LL*b[i]*tmp%MOD)%MOD;
ans=(ans+MOD)%MOD;
cout << ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
solve();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4096kb
input:
4 1 1 1 1 2 2 2 2
output:
999999815
result:
wrong answer 1st lines differ - expected: '6', found: '999999815'
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 4224kb
input:
100 948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...
output:
578285033
result:
wrong answer 1st lines differ - expected: '164439470', found: '578285033'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 1ms
memory: 4352kb
input:
500000 1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...
output:
999999987
result:
wrong answer 1st lines differ - expected: '869044223', found: '999999987'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%