Submission #1356690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1356690		Aviansh	Flooding Wall (BOI24_wall)	C++20	0 / 100	1 ms	344 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:48: warning: narrowing conversion of 'po[(mult - ((int)curr))]' from 'long long int' to 'int' [-Wnarrowing]
   67 |             lefcnt.push_back({a[0],po[mult-curr]});
      |                                    ~~~~~~~~~~~~^
Main.cpp:86:48: warning: narrowing conversion of 'po[(mult - ((int)curr))]' from 'long long int' to 'int' [-Wnarrowing]
   86 |             rigcnt.push_back({a[0],po[mult-curr]});
      |                                    ~~~~~~~~~~~~^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30