Submission #1267222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267222		Nika533	Flooding Wall (BOI24_wall)	C++20	12 / 100	95 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],w[N];
map<int,int> mymap;

main() {
    cin>>n; p[0]=1;
    for (int i=1; i<=n; i++) cin>>a[i];
    set<int> myset;
    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]);
        myset.insert(a[i]); myset.insert(b[i]);
    }
    vector<int> vals; vals.pb(0);
    for (auto x:myset) {
        vals.pb(x);
    }
    int mx=vals.size(); mx--;
    for (int i=1; i<=mx; i++) {
        w[i]=vals[i]-vals[i-1];
        mymap[vals[i]]=i;
    }
    for (int i=1; i<=n; i++) {
        a[i]=mymap[a[i]]; b[i]=mymap[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]+=w[j];
        for (int j=a[i]+1; j<=b[i]; j++) v2[j]+=w[j];
    }
    int anss=0;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]; j++) v1[j]-=w[j];
        for (int j=a[i]+1; j<=b[i]; j++) v2[j]-=w[j];

        for (int j=a[i]+1; j<=b[i]; j++) {
            int ans=0;
            if (v1[j] && u1[j]) {
                ans+=p[n-1]*w[j];
            }
            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;
            ans=(ans*w[j])%MOD;
            anss=(anss+ans)%MOD;
        }
        for (int j=b[i]+1; j<=mx; j++) {
            int ans=0;
            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;
            ans=(ans*w[j])%MOD;
            anss=(anss+ans)%MOD;
        }

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

Compilation message (stderr)

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

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