Submission #1069968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069968		underwaterkillerwhale	Flooding Wall (BOI24_wall)	C++17	0 / 100	5 ms	12892 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 320;

int n, m;
ll a[2][N];


struct Vertex {
    Vertex *lf, *rt;
    ll val, lz1, lz2;

    Vertex () {
        lf = rt = NULL;
        val = 0;
        lz1 = lz2 = -1;
    };
    Vertex (ll _val)  {
        lf = rt = NULL;
        val = _val;
        lz1 = lz2 = -1;
    }
    Vertex (Vertex *cnode) {
        lf = cnode->lf;
        rt = cnode->rt;
        val = cnode->val;
        lz1 = cnode->lz1;
        lz2 = cnode->lz2;
    };
    Vertex (Vertex *llf, Vertex *rrt) { ///merge
		lf = llf, rt = rrt;
		lz1 = lz2 = -1;
		val = 0;
		if (lf) val += lf->val;
		if (rt) val += rt->val;
	}
};

Vertex *proot[N], *sroot[N];

struct Persistent_Segment_Tree_Lazy { ///fix update lai 2 con cua truy van range
    int m;
    Vertex *prv_Ver;

    Vertex *build (int l, int r) {
        if (l == r) {
            return new Vertex;
        }
        int mid = l + r >> 1;
        return new Vertex(build (l, mid), build (mid + 1, r));
    }

    void init (int n) {
        m = n;
        prv_Ver = build(1, m);
    }

    void getval (Vertex *cur, ll val) {
        (cur->val *= val) %= Mod;
        if (cur->lz1 != -1) (cur->lz1 *= val) %= Mod;
        else {
            if (cur->lz2 != -1) (cur->lz2 *= val) %= Mod;
            else cur->lz2 = val;
        }
    }

    void down (Vertex *cnode) {
        Vertex *lf = cnode->lf, *rt = cnode->rt;
        if (cnode->lz1 != -1) {
            lf->val = rt->val = 0;
            lf->lz1 = rt->lz1 = 0;
            lf->lz2 = rt->lz2 = -1;
            cnode->lz1 = -1;
            return;
        }
        if (cnode->lz2 != -1) {
            getval(lf, cnode->lz2);
            getval(rt, cnode->lz2);
            cnode->lz2 = -1;
            return;
        }
    }

    Vertex *update (Vertex *cnode, int l, int r, int u, int v, ll val) {
        if (l >= u && r <= v) {
            Vertex *cur = new Vertex(cnode);
            getval(cur, val);
            return cur;
        }
        int mid = l + r >> 1;
        down(cnode);
        if (mid < u) return new Vertex(cnode->lf, update(cnode->rt, mid + 1, r, u, v, val));
        else if (mid > v) return new Vertex(update(cnode->lf, l, mid, u, v, val), cnode->rt);
        else return new Vertex(update(cnode->lf, l, mid, u, v, val), update (cnode->rt, mid + 1, r, u, v, val));
    }

    Vertex *Assign (Vertex *cnode, int l, int r, int pos, ll val) {
        if (l == r) {
            return new Vertex(val);
        }
        int mid = l + r >> 1;
        down(cnode);
        if (mid < pos) return new Vertex(cnode->lf, Assign(cnode->rt, mid + 1, r, pos, val));
        else return new Vertex(Assign(cnode->lf, l, mid, pos, val), cnode->rt);
    }

    Vertex *Del (Vertex *cnode, int l, int r, int u, int v) {
        if (l >= u && r <= v) {
            Vertex *cur = new Vertex(cnode);
            cur->val = 0;
            cur->lz1 = 0;
            cur->lz2 = -1;
            return cur;
        }
        int mid = l + r >> 1;
        down(cnode);
        if (mid < u) return new Vertex (cnode->lf, Del (cnode->rt, mid + 1, r, u, v)); 
        else if (mid > v) return new Vertex (Del (cnode->lf, l, mid, u, v), cnode->rt);
        else return new Vertex (Del (cnode->lf, l, mid, u, v), Del (cnode->rt, mid + 1, r, u, v));
    }

    ll get (Vertex *cnode, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return cnode->val;
        down(cnode);
        int mid = l + r >> 1;
        return get(cnode->lf, l, mid, u, v) + get (cnode->rt, mid + 1, r, u, v);
    }

    Vertex *update (int u, int v, ll val) {
        if (u > v) return prv_Ver;
        return prv_Ver = update(prv_Ver, 1, m, u, v, val);
    }
    Vertex *Assign (int pos, ll val) {
        return prv_Ver = Assign(prv_Ver, 1, m, pos, val);
    }
    Vertex *Del (int u, int v) {
        if (u > v) return prv_Ver;
        return prv_Ver = Del (prv_Ver, 1, m, u, v);
    }
    ll get (int p, int typ, int u, int v){
        if (typ == 0) return get (proot[p], 1, m, u, v);
        else return get (sroot[p], 1, m, u, v);
    }
}pre, suf;

vector<int> vals = {0}; ///1-idx

void compress () {
    rep (i, 1, n) {
        vals.pb(a[1][i]),vals.pb(a[0][i]);
    }
    sort (ALL(vals));
    vals.resize(m = unique(ALL(vals)) - vals.begin());
    rep (i, 1, n)
    rep (k, 0, 1) {
        a[k][i] = lower_bound(ALL(vals), a[k][i]) - vals.begin() + 1;
    }
}

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[0][i];
    rep (i, 1, n) {
        cin >> a[1][i];
        if (a[1][i] <= a[0][i]) swap(a[1][i], a[0][i]);
    }
    compress();
    pre.init(m);
    suf.init(m);
    proot[0] = pre.Assign(1, 1);
    rep (i, 1, n) {
        ll valai= pre.get(i - 1, 0, 1, a[0][i]),
            valbi = pre.get(i - 1, 0, 1, a[1][i]);
        pre.update (a[1][i] + 1, m, 2);
        pre.Assign (a[0][i], valai);
        pre.Assign (a[1][i], valbi);
        proot[i] = pre.Del (1, a[0][i] - 1);
        return;

    }
    ll res = 0;
    sroot[n + 1] = suf.Assign(1, 1);
    reb (i, n, 1) {
        ll valai= suf.get(i + 1, 1, 1, a[0][i]),
            valbi = suf.get(i + 1, 1, 1, a[1][i]);
        suf.update (a[1][i] + 1, m, 2);
        suf.Assign(a[0][i], valai);
        suf.Assign(a[1][i], valbi);
        sroot[i] = suf.Del (1, a[0][i] - 1);
        rep (k, 0, 1) {
            (res += suf.get(i + 1, 1, a[k][i] + 1, m) * pre.get(i - 1, 0, a[k][i] + 1, m) % Mod * vals[a[k][i]] % Mod) %= Mod;
        }
    }
    cout << res<<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
2 + 8 * 2 - 9
4
1 1 1 1
2 2 2 2
*/

Compilation message (stderr)

Main.cpp: In member function 'Vertex* Persistent_Segment_Tree_Lazy::build(int, int)':
Main.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'Vertex* Persistent_Segment_Tree_Lazy::update(Vertex*, int, int, int, int, long long int)':
Main.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'Vertex* Persistent_Segment_Tree_Lazy::Assign(Vertex*, int, int, int, long long int)':
Main.cpp:123:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'Vertex* Persistent_Segment_Tree_Lazy::Del(Vertex*, int, int, int, int)':
Main.cpp:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'long long int Persistent_Segment_Tree_Lazy::get(Vertex*, int, int, int, int)':
Main.cpp:148:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |         int mid = l + r >> 1;
      |                   ~~^~~

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