| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1356691 | Aviansh | Flooding Wall (BOI24_wall) | C++20 | 5091 ms | 1984 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n],b[n];
for(int &i : a){
cin >> i;
}
for(int &i : b){
cin >> i;
}
long long po[n];
po[0]=1;
for(int i = 1;i<n;i++){
po[i]=po[i-1]*2;
po[i]%=mod;
}
for(int i = 0;i<n;i++){
if(a[i]>b[i])
swap(a[i],b[i]);
}
vector<array<int,2>>pts(2*n);
for(int i = 0;i<n;i++){
pts[i]={a[i],i};
pts[i+n]={b[i],i};
}
long long ans = 0;
sort(pts.begin(),pts.end());
for(int i = 1;i<n-1;i++){
vector<array<int,2>>lef;
vector<array<int,2>>rig;
for(array<int,2>pt:pts){
if(pt[1]<i){
lef.push_back(pt);
}
if(pt[1]>i){
rig.push_back(pt);
}
}
vector<array<int,2>>lefcnt,rigcnt;
///each stores cnt like so: {mxval in segment, num ways}
bool vis[n];
fill(vis,vis+n,0);
int cnvis = 0;
int mult = 0;
for(array<int,2> a : lef){
bool curr = 0;
if(!vis[a[1]]){
vis[a[1]]=1;
cnvis++;
}
else {
mult++;
curr=1;
}
if(cnvis!=i){
continue;
}
///now this is actually doable
lefcnt.push_back({a[0],po[mult-curr]});
}
cnvis = 0;
mult = 0;
for(array<int,2> a : rig){
bool curr = 0;
if(!vis[a[1]]){
vis[a[1]]=1;
cnvis++;
}
else {
mult++;
curr=1;
}
if(cnvis!=n-i-1){
continue;
}
///now this is actually doable
rigcnt.push_back({a[0],po[mult-curr]});
}
for(array<int,2> l:lefcnt){
for(array<int,2>r:rigcnt){
if(min(l[0],r[0])>a[i]){
ans+=(min(l[0],r[0])-a[i])*((l[1]*r[1])%mod);
ans%=mod;
}
if(min(l[0],r[0])>b[i]){
ans+=(min(l[0],r[0])-b[i])*((l[1]*r[1])%mod);
ans%=mod;
}
}
}
}
cout << ans;
return 0;
}
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Result | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
