Submission #1267211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267211		Nika533	Flooding Wall (BOI24_wall)	C++20	48 / 100	90 ms	12104 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define MOD 1000000007
using namespace std;

const int N=5e5+5;
int n,a[N],b[N],p[N];



main() {
    cin>>n; int mx=0; p[0]=1;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) {
        cin>>b[i]; p[i]=p[i-1]*2; p[i]%=MOD;
        if (a[i]>b[i]) swap(a[i],b[i]);
        mx=max(mx,b[i]);
    }
    vector<int> v1(mx+1,0),v2(mx+1,0);
    vector<int> u1(mx+1,0),u2(mx+1,0);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]; j++) v1[j]++;
        for (int j=a[i]+1; j<=b[i]; j++) v2[j]++;
    }
    int ans=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]; j++) v1[j]--;
        for (int j=a[i]+1; j<=b[i]; j++) v2[j]--;

        for (int j=a[i]+1; j<=b[i]; j++) {
            if (v1[j] && u1[j]) {
                ans+=p[n-1];
            }
            else if (v1[j] && u2[j]) {
                ans+=(p[n-1]-p[n-1-u2[j]]+MOD);
            }
            else if (v2[j] && u1[j]) {
                ans+=(p[n-1]-p[n-1-v2[j]]+MOD);
            }
            else if (v2[j] && u2[j]) {
                ans+=(p[i-1]-p[i-1-u2[j]]+MOD)*(p[n-i]-p[n-i-v2[j]]+MOD);
            }
            ans%=MOD;
        }
        for (int j=b[i]+1; j<=mx; j++) {
            if (v1[j] && u1[j]) {
                ans+=p[n-1]*2;
            }
            else if (v1[j] && u2[j]) {
                ans+=(p[n-1]-p[n-1-u2[j]]+MOD)*2;
            }
            else if (v2[j] && u1[j]) {
                ans+=(p[n-1]-p[n-1-v2[j]]+MOD)*2;
            }
            else if (v2[j] && u2[j]) {
                ans+=(p[i-1]-p[i-1-u2[j]]+MOD)*(p[n-i]-p[n-i-v2[j]]+MOD)*2;
            }
            ans%=MOD;
        }

        for (int j=1; j<=a[i]; j++) u1[j]++;
        for (int j=a[i]+1; j<=b[i]; j++) u2[j]++;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

Main.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main() {
      | ^~~~

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