제출 #1066177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066177		Boomyday	Flooding Wall (BOI24_wall)	C++17	70 / 100	5056 ms	174760 KiB

Main

//
// Created by adavy on 8/19/2024.
//

#include <bits/stdc++.h>


using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

#pragma GCC optimize("O3")



struct Modular {
    int value;
    static const int MOD_value = MOD;

    Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
    Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

    Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
    Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
    Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

    friend Modular mexp(Modular a, long long e);
    friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

    Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
    friend Modular operator+(Modular a, Modular const b) { return a += b; }
    friend Modular operator-(Modular a, Modular const b) { return a -= b; }
    friend Modular operator-(Modular const a) { return 0 - a; }
    friend Modular operator*(Modular a, Modular const b) { return a *= b; }
    friend Modular operator/(Modular a, Modular const b) { return a /= b; }
    friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
    friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
    friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};


Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
}


struct segtree{
    vector<Modular> lzadd, lzmul, seg;
    int n, sz;
    segtree(int n){
        this->n = n;
        sz = 1;
        while (sz < n) sz *= 2;
        lzadd.assign(2*sz,0);
        lzmul.assign(2*sz,1);
        seg.assign(2*sz,0);
    }
    // first multiply, then add

    void pushdown(int rt, int tl, int tr){
        seg[rt]*= lzmul[rt];
        seg[rt]+= lzadd[rt];
        if (tl != tr){
            lzadd[2*rt] *= lzmul[rt];
            lzmul[2*rt] *= lzmul[rt];
            lzadd[2*rt] += lzadd[rt];
            lzadd[2*rt+1] *= lzmul[rt];
            lzmul[2*rt+1] *= lzmul[rt];
            lzadd[2*rt+1] += lzadd[rt];
        }
        lzadd[rt] = 0;
        lzmul[rt] = 1;
    }

    Modular sm(int l, int r, int rt, int tl, int tr){
        pushdown(rt,tl,tr);
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return seg[rt];
        int mid = (tl+tr)/2;
        return sm(l,r,2*rt,tl,mid)+sm(l,r,2*rt+1,mid+1,tr);
    }
    void mul(Modular x, int l, int r, int rt, int tl, int tr){
        pushdown(rt,tl,tr);
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            lzadd[rt] *= x;
            lzmul[rt] *= x;
            pushdown(rt,tl,tr);
            return;
        }
        int mid = (tl+tr)/2;
        mul(x,l,r,2*rt,tl,mid);
        mul(x,l,r,2*rt+1,mid+1,tr);
        seg[rt] = seg[2*rt]+seg[2*rt+1];
    }
    void add(Modular x, int l, int r, int rt, int tl, int tr){
        pushdown(rt,tl,tr);
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            lzadd[rt] += x;
            pushdown(rt,tl,tr);
            return;
        }
        int mid = (tl+tr)/2;
        add(x,l,r,2*rt,tl,mid);
        add(x,l,r,2*rt+1,mid+1,tr);
        seg[rt] = seg[2*rt]+seg[2*rt+1];
    }
};

int n,n2;
ll top = 2e9 + 3;
set<ll> coords = {0,top};
vector<ll> A,B;
vector<ll> coords_v; // small to big
map<ll,ll> coords_ind; // big to small


pair<Modular,Modular> calculate(){
    Modular leftsum = 0;

    segtree nums(n2), vals(n2);
    nums.add(1,0,0,1,0,nums.sz-1);
    for(int i=0;i<n;++i){
        
        /*
        if (i%1000 == 0){
            cout << i << endl;
        }*/
        Modular powtwo = mexp(2, n-i-1);
        ll mn = min(coords_ind[A[i]],coords_ind[B[i]]), mx = max(coords_ind[A[i]],coords_ind[B[i]]);

        Modular max_mn = nums.sm(0,mn,1,0,nums.sz-1);
        Modular max_mx = nums.sm(0,mx,1,0,nums.sz-1);
        leftsum += max_mn*coords_v[mn]*powtwo;
        leftsum += max_mx*coords_v[mx]*powtwo;
        leftsum += vals.sm(mx+1,n2-1,1,0,vals.sz-1)*2*powtwo;
        leftsum += vals.sm(mn+1,mx,1,0,vals.sz-1)*powtwo;

        //updates
        nums.mul(2,mx+1,n2-1,1,0,nums.sz-1);
        vals.mul(2,mx+1,n2-1,1,0,vals.sz-1);
        nums.mul(0,0,mn,1,0,nums.sz-1);
        vals.mul(0,0,mn,1,0,vals.sz-1);

        //cout << "maxmn: " << max_mn << " maxmx: " << max_mx << endl;

        // add the ones with max "mn"
        nums.add(max_mn,mn,mn,1,0,nums.sz-1);
        vals.add(max_mn*coords_v[mn],mn,mn,1,0,vals.sz-1);
        // add the ones with max "mx"
        nums.add(max_mx,mx,mx,1,0,nums.sz-1);
        vals.add(max_mx*coords_v[mx],mx,mx,1,0,vals.sz-1);
        //cout << leftsum << endl;
    }

    Modular max_blox = 0;
    for(int i=0;i<n2;++i){
        max_blox += nums.sm(i,i,1,0,nums.sz-1)*coords_v[i]*n;
    }

    return {leftsum,max_blox};

}
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    //freopen("input.txt","r",stdin);
    cin >> n;
    A.resize(n); B.resize(n);

    for(int i=0;i<n;++i){
        cin >> A[i]; coords.insert(A[i]);
    }
    for(int i=0;i<n;++i){
        cin >> B[i]; coords.insert(B[i]);
    }
    coords_v = vector<ll>(coords.begin(),coords.end());

    for(int i=0;i<coords_v.size();++i){
        coords_ind[coords_v[i]] = i;
    }
   n2 = coords.size();


    Modular buildsum = 0;
    for(int i=0;i<n;++i){
        Modular powtwo = mexp(2, n-1);
        buildsum += A[i]*powtwo + B[i]*powtwo;
    }
    auto [leftsum,max_blox] = calculate();

    max_blox -= buildsum;

    reverse(A.begin(),A.end());
    reverse(B.begin(),B.end());
    auto [rightsum, max_blox2] = calculate();








    cout << leftsum+rightsum-2*buildsum-max_blox << endl;



}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:181:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     for(int i=0;i<coords_v.size();++i){
      |                 ~^~~~~~~~~~~~~~~~

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