Submission #1064860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064860		Plurm	Flooding Wall (BOI24_wall)	C++11	70 / 100	5074 ms	27776 KiB

Main

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

int a[500005];
int b[500005];
const int MOD = 1e9 + 7;
vector<int> compressor_a, compressor_b;
class QueryMaintainer {
  public:
    int *FTmn;
    int *FTmx;
    int sz;
    QueryMaintainer() {
        sz = 0;
        FTmn = new int[compressor_a.size() + 2];
        memset(FTmn, 0, (compressor_a.size() + 2) * 4);
        FTmx = new int[compressor_b.size() + 2];
        memset(FTmx, 0, (compressor_b.size() + 2) * 4);
        pridx_a = pridx_b = 0;
    }
    ~QueryMaintainer() {
        delete[] FTmn;
        delete[] FTmx;
    }
    void mn_add(int idx, int amt) {
        while (idx <= compressor_a.size() + 1) {
            FTmn[idx] += amt;
            idx++;
        }
    }
    inline int mn_sum(const int &idx) { return FTmn[idx]; }
    void mx_add(int idx, int amt) {
        while (idx <= compressor_b.size() + 1) {
            FTmx[idx] += amt;
            idx++;
        }
    }
    inline int mx_sum(const int &idx) { return FTmx[idx]; }
    void insert(int a, int b) {
        sz++;
        mn_add(full_cpa(a) + 1, 1);
        mx_add(full_cpb(b) + 1, 1);
    }
    void erase(int a, int b) {
        sz--;
        mn_add(full_cpa(a) + 1, -1);
        mx_add(full_cpb(b) + 1, -1);
    }
    int pridx_a, pridx_b;
    inline int full_cpa(const int &p) {
        return lower_bound(compressor_a.begin(), compressor_a.end(), p) -
               compressor_a.begin();
    }
    inline int full_cpb(const int &p) {
        return lower_bound(compressor_b.begin(), compressor_b.end(), p) -
               compressor_b.begin();
    }
    inline int cpa(const int &p) {
        while (pridx_a < compressor_a.size() && compressor_a[pridx_a] < p)
            pridx_a++;
        return pridx_a;
    }
    inline int cpb(const int &p) {
        while (pridx_b < compressor_b.size() && compressor_b[pridx_b] < p)
            pridx_b++;
        return pridx_b;
    }
};
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_a =
            lower_bound(compressor_a.begin(), compressor_a.end(), *it) -
            compressor_a.begin();
        pref.pridx_b =
            lower_bound(compressor_b.begin(), compressor_b.end(), *it) -
            compressor_b.begin();
        suff.pridx_a =
            lower_bound(compressor_a.begin(), compressor_a.end(), *it + 1) -
            compressor_a.begin();
        suff.pridx_b =
            lower_bound(compressor_b.begin(), compressor_b.end(), *it + 1) -
            compressor_b.begin();
        while (it != possible.end()) {
            int p = *it;
            int cpap = pref.cpa(p);
            int cpbp = pref.cpb(p);
            int cpapp = pref.cpa(p + 1);
            int cpbpp = pref.cpb(p + 1);
            int alpha = pref.FTmx[cpbp];
            int beta = pref.FTmx[cpbpp] - pref.FTmx[cpbp];
            int gamma = pref.FTmn[cpapp] - pref.FTmn[cpap];
            int delta = pref.sz - pref.FTmn[cpapp];
            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;
            cpap = suff.cpa(p + 1);
            cpbp = suff.cpb(p + 1);
            cpapp = suff.cpa(p + 2);
            cpbpp = suff.cpb(p + 2);
            int alpha_ = suff.FTmx[cpbp];
            int beta_ = suff.FTmx[cpbpp] - suff.FTmx[cpbp];
            int gamma_ = suff.FTmn[cpapp] - suff.FTmn[cpap];
            int delta_ = suff.sz - suff.FTmn[cpapp];
            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_a =
            lower_bound(compressor_a.begin(), compressor_a.end(), it->first) -
            compressor_a.begin();
        pref.pridx_b =
            lower_bound(compressor_b.begin(), compressor_b.end(), it->first) -
            compressor_b.begin();
        suff.pridx_a =
            lower_bound(compressor_a.begin(), compressor_a.end(), it->first) -
            compressor_a.begin();
        suff.pridx_b =
            lower_bound(compressor_b.begin(), compressor_b.end(), it->first) -
            compressor_b.begin();
        while (it != possible.end()) {
            int q = it->first;
            int cpap = pref.cpa(q);
            int cpbp = pref.cpb(q);
            int cpapp = pref.cpa(q + 1);
            int cpbpp = pref.cpb(q + 1);
            int alpha = pref.FTmx[cpbp];
            int beta = pref.FTmx[cpbpp] - pref.FTmx[cpbp];
            int gamma = pref.FTmn[cpapp] - pref.FTmn[cpap];
            int delta = pref.sz - pref.FTmn[cpapp];
            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);
            cpap = suff.cpa(q);
            cpbp = suff.cpb(q);
            cpapp = suff.cpa(q + 1);
            cpbpp = suff.cpb(q + 1);
            int alpha_ = suff.FTmx[cpbp];
            int beta_ = suff.FTmx[cpbpp] - suff.FTmx[cpbp];
            int gamma_ = suff.FTmn[cpapp] - suff.FTmn[cpap];
            int delta_ = suff.sz - suff.FTmn[cpapp];
            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];
        if (a[i] > b[i])
            swap(a[i], b[i]);
        compressor_a.push_back(a[i]);
        compressor_b.push_back(b[i]);
    }
    sort(compressor_a.begin(), compressor_a.end());
    compressor_a.resize(unique(compressor_a.begin(), compressor_a.end()) -
                        compressor_a.begin());
    sort(compressor_b.begin(), compressor_b.end());
    compressor_b.resize(unique(compressor_b.begin(), compressor_b.end()) -
                        compressor_b.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: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 <= compressor_a.size() + 1) {
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'void QueryMaintainer::mx_add(int, int)':
Main.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while (idx <= compressor_b.size() + 1) {
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'int QueryMaintainer::cpa(const int&)':
Main.cpp:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (pridx_a < compressor_a.size() && compressor_a[pridx_a] < p)
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'int QueryMaintainer::cpb(const int&)':
Main.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (pridx_b < compressor_b.size() && compressor_b[pridx_b] < p)
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int solve_exact(int)':
Main.cpp:104:17: warning: unused variable 'epsilon' [-Wunused-variable]
  104 |             int epsilon = pref.sz - alpha - beta - gamma - delta;
      |                 ^~~~~~~
Main.cpp: In function 'int solve_geq(int)':
Main.cpp:202:17: warning: unused variable 'epsilon_' [-Wunused-variable]
  202 |             int epsilon_ = suff.sz - alpha_ - beta_ - gamma_ - delta_;
      |                 ^~~~~~~~

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