Submission #1064815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064815		Plurm	Flooding Wall (BOI24_wall)	C++11	56 / 100	5054 ms	13772 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int a[500005];
int b[500005];
const int MOD = 1e9 + 7;
vector<int> compressor;
class QueryMaintainer {
  public:
    vector<int> FTmn, FTmx;
    int sz;
    QueryMaintainer() {
        sz = 0;
        FTmn.resize(compressor.size() + 2, 0);
        FTmx.resize(compressor.size() + 2, 0);
        pridx = 0;
    }
    void mn_add(int idx, int amt) {
        while (idx < FTmn.size()) {
            FTmn[idx] += amt;
            idx++;
        }
    }
    inline int mn_sum(const int &idx) { return FTmn[idx]; }
    void mx_add(int idx, int amt) {
        while (idx < FTmx.size()) {
            FTmx[idx] += amt;
            idx++;
        }
    }
    inline int mx_sum(const int &idx) { return FTmx[idx]; }
    void insert(int a, int b) {
        sz++;
        mn_add(cp(a), 1);
        mx_add(cp(b), 1);
    }
    void erase(int a, int b) {
        sz--;
        mn_add(cp(a), -1);
        mx_add(cp(b), -1);
    }
    int pridx;
    inline int cp(const int &p) {
        if (pridx == compressor.size())
            pridx--;
        while (pridx > 0 && compressor[pridx] > p)
            pridx--;
        while (pridx < compressor.size() && compressor[pridx] < p)
            pridx++;
        return pridx;
    }
    int alpha(int p) { return mx_sum(cp(p) - 1); }
    int beta(int p) { return mx_sum(cp(p + 1) - 1) - mx_sum(cp(p) - 1); }
    int gamma(int p) { return mn_sum(cp(p + 1) - 1) - mn_sum(cp(p) - 1); }
    int delta(int p) { return sz - mn_sum(cp(p + 1) - 1); }
    // epsilon = size() - alpha - beta - gamma - delta
};
int pow2[500005];
inline int fastmod(const int &a) { return a >= MOD ? a - MOD : a; }
int solve_exact(int n) {
    int ans = 0;
    QueryMaintainer pref, suff;
    for (int i = 0; i < n; i++)
        suff.insert(a[i], b[i]);
    set<int> possible;
    for (int i = 0; i < n; i++) {
        possible.insert(a[i]);
        possible.insert(b[i]);
        suff.erase(a[i], b[i]);
        auto it = possible.lower_bound(min(a[i], b[i]));
        pref.pridx = lower_bound(compressor.begin(), compressor.end(), *it) -
                     compressor.begin();
        suff.pridx =
            lower_bound(compressor.begin(), compressor.end(), *it + 1) -
            compressor.begin();
        while (it != possible.end()) {
            int p = *it;
            int alpha = pref.alpha(p);
            int beta = pref.beta(p);
            int gamma = pref.gamma(p);
            int delta = pref.delta(p);
            int epsilon = pref.sz - alpha - beta - gamma - delta;
            // Case left = p
            int mem_left =
                delta == 0
                    ? 1ll * pow2[alpha] *
                          fastmod(pow2[beta] + (gamma == 0 ? MOD - 1 : 0)) % MOD
                    : 0;
            int alpha_ = suff.alpha(p + 1);
            int beta_ = suff.beta(p + 1);
            int gamma_ = suff.gamma(p + 1);
            int delta_ = suff.delta(p + 1);
            int epsilon_ = suff.sz - alpha_ - beta_ - gamma_ - delta_;
            int g =
                gamma_ + delta_ != 0
                    ? pow2[suff.sz]
                    : fastmod((epsilon_ != 0
                                   ? 1ll * fastmod(pow2[epsilon_] + MOD - 1) *
                                         pow2[alpha_ + beta_] % MOD
                                   : 0) +
                              1ll * pow2[alpha_] *
                                  fastmod(pow2[beta_] + MOD - 1) % MOD);
            if (p > a[i]) {
                ans += 1ll * mem_left * g % MOD * (p - a[i]) % MOD;
                ans = fastmod(ans);
            }
            if (p > b[i]) {
                ans += 1ll * mem_left * g % MOD * (p - b[i]) % MOD;
                ans = fastmod(ans);
            }
            it++;
        }
        pref.insert(a[i], b[i]);
    }
    return ans;
}
int solve_geq(int n) {
    int ans = 0;
    QueryMaintainer pref, suff;
    map<int, int> possible;
    for (int i = 0; i < n; i++) {
        suff.insert(a[i], b[i]);
        possible[a[i]]++;
        possible[b[i]]++;
    }
    for (int i = 0; i < n; i++) {
        possible[a[i]]--;
        possible[b[i]]--;
        if (possible[a[i]] == 0)
            possible.erase(a[i]);
        if (possible[b[i]] == 0)
            possible.erase(b[i]);
        suff.erase(a[i], b[i]);
        auto it = possible.lower_bound(min(a[i], b[i]));
        pref.pridx =
            lower_bound(compressor.begin(), compressor.end(), it->first) -
            compressor.begin();
        suff.pridx =
            lower_bound(compressor.begin(), compressor.end(), it->first) -
            compressor.begin();
        while (it != possible.end()) {
            int q = it->first;
            int alpha = pref.alpha(q);
            int beta = pref.beta(q);
            int gamma = pref.gamma(q);
            int delta = pref.delta(q);
            int epsilon = pref.sz - alpha - beta - gamma - delta;
            // Case left >= q
            int mem_left =
                gamma + delta != 0
                    ? pow2[pref.sz]
                    : fastmod((epsilon != 0
                                   ? 1ll * fastmod(pow2[epsilon] + MOD - 1) *
                                         pow2[alpha + beta] % MOD
                                   : 0) +
                              1ll * pow2[alpha] *
                                  fastmod(pow2[beta] + MOD - 1) % MOD);
            int alpha_ = suff.alpha(q);
            int beta_ = suff.beta(q);
            int gamma_ = suff.gamma(q);
            int delta_ = suff.delta(q);
            int epsilon_ = suff.sz - alpha_ - beta_ - gamma_ - delta_;
            // Case left >= q, right = q
            int e =
                delta_ == 0
                    ? 1ll * pow2[alpha_] *
                          fastmod(pow2[beta_] + (gamma_ == 0 ? MOD - 1 : 0)) %
                          MOD
                    : 0;
            if (q > a[i]) {
                ans += 1ll * mem_left * e % MOD * (q - a[i]) % MOD;
                ans = fastmod(ans);
            }
            if (q > b[i]) {
                ans += 1ll * mem_left * e % MOD * (q - b[i]) % MOD;
                ans = fastmod(ans);
            }
            it++;
        }
        pref.insert(a[i], b[i]);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    pow2[0] = 1;
    for (int i = 1; i <= n; i++)
        pow2[i] = 2 * pow2[i - 1] % MOD;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        compressor.push_back(a[i]);
        compressor.push_back(b[i]);
        if (a[i] > b[i])
            swap(a[i], b[i]);
    }
    sort(compressor.begin(), compressor.end());
    compressor.resize(unique(compressor.begin(), compressor.end()) -
                      compressor.begin());
    cout << fastmod(solve_exact(n) + solve_geq(n)) << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void QueryMaintainer::mn_add(int, int)':
Main.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         while (idx < FTmn.size()) {
      |                ~~~~^~~~~~~~~~~~~
Main.cpp: In member function 'void QueryMaintainer::mx_add(int, int)':
Main.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         while (idx < FTmx.size()) {
      |                ~~~~^~~~~~~~~~~~~
Main.cpp: In member function 'int QueryMaintainer::cp(const int&)':
Main.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if (pridx == compressor.size())
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while (pridx < compressor.size() && compressor[pridx] < p)
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int solve_exact(int)':
Main.cpp:82:17: warning: unused variable 'epsilon' [-Wunused-variable]
   82 |             int epsilon = pref.sz - alpha - beta - gamma - delta;
      |                 ^~~~~~~
Main.cpp: In function 'int solve_geq(int)':
Main.cpp:162:17: warning: unused variable 'epsilon_' [-Wunused-variable]
  162 |             int epsilon_ = suff.sz - alpha_ - beta_ - gamma_ - delta_;
      |                 ^~~~~~~~

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