제출 #1247751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247751		Matthewwww	Flooding Wall (BOI24_wall)	C++17	100 / 100	4716 ms	188392 KiB

Main

#pragma GCC target("avx2", "bmi")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
#include <sys/mman.h>
#include <sys/stat.h>
const ll mod = 1e9+7;
const ll i2 = 5e8+4;
 
struct state {
	ll m, c, num;
	state(): m(0), c(0), num(0) {}
	state (ll a, ll b, ll d): m(a%mod), c(b%mod), num(d%mod) {}
	state operator+ (state b) {
		return state((m+b.m)%mod, (c+b.c)%mod, (num+b.num)%mod);
	}
	state dbg() {
		err << m << " " << c << " " << num << "\n";
		return *this;
	}
};
 
int m;
 
struct Sgt;
Sgt *newSgt();
 
struct Sgt {
	state val;
	bool reset;
	ll add;
	ll aw;
	Sgt *lft, *rht;
	Sgt (): val(), reset(false), add(0), aw(1), lft(nullptr), rht(nullptr) {}
	void push () {
		if (!lft) {
			lft = newSgt();
			rht = newSgt();
		}
		if (reset) {
			lft->reset = rht->reset = true;
			lft->val = rht->val = state();
			lft->add = rht->add = 0;
		}
		reset = false;
		if (aw != 1) {
			(lft->aw *= aw) %= mod;
			(rht->aw *= aw) %= mod;
			(lft->val.m *= aw) %= mod;
			(rht->val.m *= aw) %= mod;
			(lft->val.c *= aw) %= mod;
			(rht->val.c *= aw) %= mod;
			(lft->val.num *= aw) %= mod;
			(rht->val.num *= aw) %= mod;
		}
		aw = 1;
		if (add) {
			(lft->add += add) %= mod;
			(rht->add += add) %= mod;
			(lft->val.c += add*lft->val.num) %= mod;
			(rht->val.c += add*rht->val.num) %= mod;
		}
		add = 0;
	}
#define lc tl, tl+tr>>1
#define rc tl+tr>>1, tr
	void clear (int r, int tl = 0, int tr = m) {
		if (tl >= r) return;
		if (r >= tr) {
			val = state(0, 0, 0);
			reset = true;
			add = 0;
			aw = 1;
			return;
		}
		push();
		lft->clear(r, lc);
		rht->clear(r, rc);
		val = lft->val+rht->val;
	}
	void update (int i, state x, int tl = 0, int tr = m) {
		if (tl == tr-1) return void(val = x);
		push();
		if (i < tl+tr>>1) lft->update(i, x, lc);
		else rht->update(i, x, rc);
		val = lft->val+rht->val;
	}
	void inc (int l, int r, ll c, int tl = 0, int tr = m) {
		if (l >= tr || tl >= r) return;
		if (l <= tl && r >= tr) {
			(val.c += c*val.num) %= mod;
			(add += c) %= mod;
			return;
		}
		push();
		lft->inc(l, r, c, lc);
		rht->inc(l, r, c, rc);
		val = lft->val+rht->val;
	}
	void doub (int l, int r, int tl = 0, int tr = m) {
		if (l >= tr || tl >= r) return;
		if (l <= tl && r >= tr) {
			(val.m *= 2) %= mod;
			(val.c *= 2) %= mod;
			(val.num *= 2) %= mod;
			return void((aw *= 2) %= mod);
		}
		push();
		lft->doub(l, r, lc);
		rht->doub(l, r, rc);
		val = lft->val+rht->val;
	}
	state query (int l, int r, int tl = 0, int tr = m) {
		if (l >= tr || tl >= r) return state();
		if (l <= tl && r >= tr) return val;
		push();
		return lft->query(l, r, lc)+rht->query(l, r, rc);
	}
} pool[2000000];
int upto = 0;
Sgt *newSgt () {
	return &pool[upto++];
}
 
struct FastInput {
    char *ptr;  // This is where all the chars get read into
    struct stat fileStatus;  // A weird struct that we need in order to know the size of the file
 
    FastInput() {
        int fileDescriptor = fileno(stdin);  // Gets like the ID (??) of stdin. It's an int somehow.
        fstat(fileDescriptor, &fileStatus);  // Gets the file status by passing in the ID
        ptr = (char*) mmap(  // This is the cool function that reads in ALL the input at once
            0,                   // Where to start (we start from the start obv)
            fileStatus.st_size,  // How big the file is (this is why we need fileStatus)
            PROT_READ,           // How we want to use this file — we want to read it
            MAP_PRIVATE,         // Extra flags. This one is the fastest (trust me I tested a bunch of them)
            fileDescriptor,      // Once again the ID of the stream to read from
            0                    // "offset" idk what this does but we're starting at the start so it's probs fine
        );
        madvise(  // This makes reading EVEN faster
            ptr,
            fileStatus.st_size,
            MADV_SEQUENTIAL  // We tell it we read all data sequentially. Which is fast. I buy.
        );
    }
 
    void operator>>(unsigned &x) {
        while (*ptr <= ' ') ++ptr;  // Skip all the whitespace (apparently newline is same as whitespace)
        x = *ptr++ & 15;  // For digits 0-9 last four bits are just the digit lol
        while (*ptr > ' ') x = x * 10 + (*ptr++ & 15);  // Keep reading until whitespace
    }
} qin;
// thanks nathan for the fastio
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	unsigned _n;
	qin >> _n;
	n = _n;
	vector<pair<ll, ll>> vt(n);
	for (int i = 0; i < n; i++) {
		unsigned a;
		qin >> a;
		vt[i].f = a;
	}
	for (int i = 0; i < n; i++) {
		unsigned a;
		qin >> a;
		vt[i].s = a;
	}
	for (auto &i: vt) if (i.f > i.s) swap(i.f, i.s);
	vector<int> cc;
	for (auto i: vt) {
		cc.push_back(i.f);
		cc.push_back(i.s);
	}
	cc.push_back(0);
	cc.push_back(1e9+1);
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	m = cc.size();
	vector<pair<int, int>> ord(n);
	for (int i = 0; i < n; i++) {
		ord[i].f = lower_bound(cc.begin(), cc.end(), vt[i].f)-cc.begin();
		ord[i].s = lower_bound(cc.begin(), cc.end(), vt[i].s)-cc.begin();
	}
	vector<pair<state, state>> lf(n), rh(n);
	Sgt sgt;
	sgt.update(0, state(0, 0, 1));
	for (int i = 0; i < n; i++) {
		lf[i].f = sgt.query(0, ord[i].f);
		lf[i].s = sgt.query(0, ord[i].s);
		sgt.doub(ord[i].s, m);
		auto a = sgt.query(0, ord[i].f+1);
		auto b = lf[i].s;
		a = state(vt[i].f*a.num, a.m*i+a.c-vt[i].f*i%mod*a.num, a.num);
		b = state(vt[i].s*b.num, b.m*i+b.c-vt[i].s*i%mod*b.num-vt[i].s*b.num, b.num);
		sgt.update(ord[i].f, a);
		sgt.inc(ord[i].s, m, (-vt[i].f-vt[i].s)*i2%mod);
		sgt.update(ord[i].s, b+sgt.query(ord[i].s, ord[i].s+1));
		sgt.clear(ord[i].f);
		sgt.inc(ord[i].f, ord[i].s, -vt[i].f);
	}
	sgt.clear(m);
	sgt.update(0, state(0, 0, 1));
	for (int i = n; i--;) {
		rh[i].f = sgt.query(0, ord[i].f+1);
		rh[i].s = sgt.query(0, ord[i].s+1);
		sgt.doub(ord[i].s, m);
		auto a = rh[i].f;
		auto b = sgt.query(0, ord[i].s);
		a = state(vt[i].f*a.num, a.m*(-i)+a.c-vt[i].f*(-i)%mod*a.num, a.num);
		b = state(vt[i].s*b.num, b.m*(-i)+b.c-vt[i].s*(-i)%mod*b.num-vt[i].s*b.num, b.num);
		sgt.update(ord[i].f, a);
		sgt.inc(ord[i].s, m, (-vt[i].f-vt[i].s)*i2%mod);
		sgt.update(ord[i].s, b+sgt.query(ord[i].s, ord[i].s+1));
		sgt.clear(ord[i].f);
		sgt.inc(ord[i].f, ord[i].s, -vt[i].f);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans += lf[i].f.num*(rh[i].f.m*(-i)%mod+rh[i].f.c);
		ans += rh[i].f.num*(lf[i].f.m*(i)%mod+lf[i].f.c);
		ans %= mod;
		ans += lf[i].s.num*(rh[i].s.m*(-i)%mod+rh[i].s.c);
		ans += rh[i].s.num*(lf[i].s.m*(i)%mod+lf[i].s.c);
		ans %= mod;
	}
	cout << (ans%mod+mod)%mod << "\n";
}
 
// no llama :(

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