Submission #1113101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113101		cpptowin	Flooding Wall (BOI24_wall)	C++17	100 / 100	3979 ms	244136 KiB

Main

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if(x < 0) x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if(x < 0) x += mod;
}
int n;
pii a[maxn];
vi nen;
int sum = 0;
int Pow(int a,int n)
{
    int ans = 1;
    for( ; n ; n >>= 1, a = ((a * a) % mod + mod) % mod) if(n & 1)
        {
            ans = ((ans * a) % mod + mod) % mod;
        }
    return ans;
}
int p[maxn];
map<int,vi> ke;
int inv2 = Pow(2,mod - 2);
int cnt[maxn];
struct STLEFT
{
    vector<array<int,2>> st;
    vi lazy;
    int n;
    STLEFT(int _n) : n(_n)
    {
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10,1);
    }
    void build(int id,int l,int r)
    {
        if(l == r)
        {
            st[id][1] = p[n - 1];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1,l,mid);
        build(id << 1 | 1,mid + 1,r);
    }
    void down(int id)
    {
        lazy[id << 1] = lazy[id << 1] * lazy[id] % mod;
        lazy[id << 1 | 1] = lazy[id << 1 | 1] * lazy[id] % mod;
        st[id << 1][0] = st[id << 1][0] * lazy[id] % mod;
        st[id << 1 | 1][0] = st[id << 1 | 1][0] * lazy[id] % mod;
        st[id << 1][1] = st[id << 1][1] * lazy[id] % mod;
        st[id << 1 | 1][1] =  st[id << 1 | 1][1] * lazy[id] % mod;
        lazy[id] = 1;
    }
    void update(int id,int l,int r,int x)
    {
        if(l > x or r < x) return;
        if(l == r)
        {
            add(st[id][0],(l - 1) * st[id][1]);
//            cout << l << 'x' << st[id][0];en;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        update(id << 1,l,mid,x);
        update(id << 1 | 1,mid + 1,r,x);
        st[id][0] = (st[id << 1][0] + st[id << 1 | 1][0]) % mod;
    }
    void change(int id,int l,int r,int u,int v,int val)
    {
        if(l > v or r < u) return;
        if(u <= l and r <= v)
        {
            st[id][0] = st[id][0] * val % mod;
            st[id][1] = st[id][1] * val % mod;
            lazy[id] = lazy[id] * val % mod;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        change(id << 1,l,mid,u,v,val);
        change(id << 1 | 1,mid + 1,r,u,v,val);
        st[id][0] = (st[id << 1][0] + st[id << 1 | 1][0]) % mod;
    }
    void up(int x)
    {
        update(1,1,n,x);
        if(cnt[x] == 1)
            change(1,1,n,x + 1,n,inv2);
        else change(1,1,n,x + 1,n,0);
//        cout << st[1][0] << ' ' << x << ' ' << cnt[x];en;
    }
};
struct STRIGHT
{
    vector<array<int,2>> st;
    vi lazy;
    int n;
    STRIGHT(int _n) : n(_n)
    {
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10,1);
    }
    void build(int id,int l,int r)
    {
        if(l == r)
        {
            st[id][1] = p[n - 1];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1,l,mid);
        build(id << 1 | 1,mid + 1,r);
    }
    void down(int id)
    {
        lazy[id << 1] = lazy[id << 1] * lazy[id] % mod;
        lazy[id << 1 | 1] = lazy[id << 1 | 1] * lazy[id] % mod;
        st[id << 1][1] = st[id << 1][1] * lazy[id] % mod;
        st[id << 1 | 1][1] =  st[id << 1 | 1][1] * lazy[id] % mod;
        st[id << 1][0] = st[id << 1][0] * lazy[id] % mod;
        st[id << 1 | 1][0] = st[id << 1 | 1][0] * lazy[id] % mod;
        lazy[id] = 1;
    }
    void update(int id,int l,int r,int x)
    {
        if(l > x or r < x) return;
        if(l == r)
        {
            add(st[id][0],l * st[id][1]);
            return;
        }
        down(id);
        int mid = l + r >> 1;
        update(id << 1,l,mid,x);
        update(id << 1 | 1,mid + 1,r,x);
        st[id][0] = (st[id << 1][0] + st[id << 1 | 1][0]) % mod;
    }
    void change(int id,int l,int r,int u,int v,int val)
    {
        if(l > v or r < u) return;
        if(u <= l and r <= v)
        {
            st[id][0] = st[id][0] * val % mod;
            st[id][1] = st[id][1] * val % mod;
            lazy[id] = lazy[id] * val % mod;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        change(id << 1,l,mid,u,v,val);
        change(id << 1 | 1,mid + 1,r,u,v,val);
        st[id][0] = (st[id << 1][0] + st[id << 1 | 1][0]) % mod;
    }
    void up(int x)
    {
        update(1,1,n,x);
        if(cnt[x] == 1)
            change(1,1,n,1,x - 1,inv2);
        else change(1,1,n,1,x - 1,0);
    }
};
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    p[0] = 1;
    fo(i,1,maxn - 1) p[i] = p[i - 1] * 2 % mod;
    cin >> n;
    fo(i,1,n)
    {
        cin >> a[i].fi;
        nen.pb(a[i].fi);
        ke[a[i].fi].pb(i);
    }
    fo(i,1,n)
    {
        cin >> a[i].se;
        nen.pb(a[i].se);
        ke[a[i].se].pb(i);
    }
    sort(all(nen));
    UNIQUE(nen);
    fo(i,1,n)
    {
        add(sum,p[n - 1] * a[i].fi);
        add(sum,p[n - 1] * a[i].se);
    }
//    cout << sum;
//    en;
    sum = mod - sum;
    reverse(all(nen));
    STLEFT tl(n);
    tl.build(1,1,n);
    STRIGHT tr(n);
    tr.build(1,1,n);
    int pre = -1;
    for(int it : nen)
    {
        if(pre != -1)
        {
            add(sum,(pre - it) * tr.st[1][0]);
            del(sum,(pre - it) * tl.st[1][0]);
        }
        for(int pos : ke[it])
        {
            cnt[pos]++;
            tl.up(pos);
            tr.up(pos);
        }
//        cout << it;
//        en;
//        for(int pos : ke[it]) cout << pos << ' ';
//        en;
//        cout << tr.st[1][0] << ' ' << tl.st[1][0];
//        en;
        pre = it;
    }
    if(pre != -1)
    {
        add(sum,(pre) * tr.st[1][0]);
        del(sum,(pre) * tl.st[1][0]);
    }
    cout << sum;
}

Compilation message (stderr)

Main.cpp: In member function 'void STLEFT::build(long long int, long long int, long long int)':
Main.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void STLEFT::update(long long int, long long int, long long int, long long int)':
Main.cpp:116:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void STLEFT::change(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void STRIGHT::build(long long int, long long int, long long int)':
Main.cpp:163:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void STRIGHT::update(long long int, long long int, long long int, long long int)':
Main.cpp:186:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void STRIGHT::change(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:202:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  202 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: At global scope:
Main.cpp:215:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  215 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:221:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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