Submission #1269163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269163		dosts	Flooding Wall (BOI24_wall)	C++20	100 / 100	4564 ms	160808 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;

int add(int x,int y) {
    if ((x + y) >= MOD) return x + y - MOD;
    return x + y;
}

int mult(int x,int y) {
    return (1LL * x * y) % MOD;
}

int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x, y >> 1);
    e = mult(e, e);
    if (y & 1) e = mult(e, x);
    return e;
}

struct ST {
    //Range mult Range sum
    vi t,lazy;

    ST(int nn) {
        t.assign(4*nn+1,1);
        lazy.assign(4*nn+1,1);
    }
    void reset(int nn) {
        t.assign(4*nn+1,1);
        lazy.assign(4*nn+1,1);
    }

    void push(int node,bool leaf) {
        t[node] = mult(t[node],lazy[node]);
        if (!leaf) {
            lazy[2*node]=mult(lazy[2*node],lazy[node]);
            lazy[2*node+1]=mult(lazy[2*node+1],lazy[node]);
        }
        lazy[node] = 1;
    }


    void update(int node,int l,int r,int L,int R,int v) {
        push(node,l==r);
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            lazy[node] = mult(lazy[node],v);
            push(node,l==r);
            return;
        }
        int m = (l+r) >> 1;
        update(2*node,l,m,L,R,v);
        update(2*node+1,m+1,r,L,R,v);
        t[node] = add(t[2*node],t[2*node+1]);
    }

    int query(int node,int l,int r,int L,int R) {
        if (L > R) return 0;
        push(node,l==r);
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return add(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
    }
};

void solve() {
    int n;
    cin >> n;
    vi a(n),b(n);
    for (int i=0;i<n;i++) cin >> a[i];
    for (int i=0;i<n;i++) cin >> b[i];
    map<int,vi> whereis;
    for (int i = 0;i<n;i++) {
        whereis[a[i]].push_back(i);
        whereis[b[i]].push_back(i);
    }
    vi vals;
    for (auto& it : whereis) {
        vals.push_back(it.ff);
        sort(all(it.ss));
        it.ss.erase(unique(all(it.ss)),it.ss.end());
    }
    vi ctr(n,0);
    int ans = 0;
    int ptr = 0;
    ST st(n);
    int prv = 0;
    for (int i = 0;i<n;i++) st.update(1,1,n,i+1,i+1,expo(2,n-i-1));
    for (int i = 0;i<vals.size();i++){
        int v = vals[i];
        for (auto p : whereis[v]) {
            if (a[p] == v) ctr[p]++;
            if (b[p] == v) ctr[p]++;
            st.update(1,1,n,p+1,n,ctr[p]);
        }
        while (ptr<n && ctr[ptr]) ptr++;
        ans = add(ans,mult(add(st.query(1,1,n,1,ptr),MOD-prv),v));
        prv=st.query(1,1,n,1,ptr);
    }
    st.reset(n);
    for (int i = 0;i<n;i++) st.update(1,1,n,i+1,i+1,expo(2,i));
    ptr = n-1;
    prv = 0;
    int prvprd = 0;
    ctr.assign(n,0);

    int prd = 1;
    for (int i = 0;i<vals.size();i++){
        int v = vals[i];
        for (auto p : whereis[v]) {
            if (a[p] == v) ctr[p]++;
            if (b[p] == v) ctr[p]++;
            if (ctr[p] == 2) prd = mult(prd,2);
            st.update(1,1,n,1,p+1,ctr[p]);
        }
        while (ptr>=0 && ctr[ptr]) ptr--;
        ans = add(ans,mult(add(st.query(1,1,n,ptr+2,n),MOD-prv),v));
        prv=st.query(1,1,n,ptr+2,n);
        if (ptr == -1) ans = add(ans,MOD-mult(n,mult(v,add(prd,MOD-prvprd))));
        if (ptr == -1) prvprd = prd;
    }
    for (int i = 0;i<n;i++) ans=add(ans,MOD-mult(expo(2,n-1),add(a[i],b[i])));
    cout << ans << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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