제출 #534841

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534841		wiwiho	Fire (JOI20_ho_t5)	C++14	100 / 100	522 ms	43972 KiB

ho_t5

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

int lowbit(int x){
    return x & -x;
}

struct BIT{
    vector<ll> bit;
    void init(int n){
        bit.resize(n + 1);
    }
    void modify(int x, ll v){
        for(; x < bit.size(); x += lowbit(x)) bit[x] += v;
    }
    ll query(int x){
        x = min(x, (int)bit.size() - 1);
        ll ans = 0;
        for(; x > 0; x -= lowbit(x)) ans += bit[x];
        return ans;
    }
};

struct BITSUM{
    BIT bit1, bit2;
    int offset;

    void init(int n){
        bit1.init(2 * n + 1);
        bit2.init(2 * n + 1);
        offset = n;
    }

    void modify(int x, ll v){
        x += offset;
        bit1.modify(x, v);
        bit2.modify(x, x * v);
    }

    void modify(int l, int r, ll v){
        modify(l, v);
        modify(r + 1, -v);
    }

    ll query(int x){
        x += offset;
        return (x + 1) * bit1.query(x) - bit2.query(x);
    }

    ll query(int l, int r){
        return query(r) - query(l - 1);
    }

    void off(){
        modify(0, 0, query(1, 1));
        offset--;
    }
};

int main(){
    StarBurstStream

    int n, q;
    cin >> n >> q;

    vector<ll> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<vector<pii>> qry(n + 1);
    for(int i = 1; i <= q; i++){
        int t, l, r;
        cin >> t >> l >> r;
        qry[l - 1].eb(mp(t, -i));
        qry[r].eb(mp(t, i));
    }

    BITSUM bit1, bit2, bit3;
    bit1.init(n); bit2.init(n); bit3.init(n);
    ll con = 0;

    vector<int> pr(n + 1, -1);
    vector<int> sz(n + 1, 1);

    auto remove = [&](int i){
        if(pr[i] == -1) return;
        ll dp = i - pr[i] - 1;
        ll da = a[pr[i]] - a[i];
        bit1.modify(1, sz[i] + dp, -da);
        bit2.modify(1, sz[i] + dp, da);
        sz[pr[i]] += sz[i];
    };

    auto add = [&](int i){
        if(pr[i] == -1) return;
        ll dp = i - pr[i] - 1;
        ll da = a[pr[i]] - a[i];
        bit1.modify(1, 1 + dp, da);
        bit3.modify(1, dp, da);
        con += -dp * da;
    };

    auto query = [&](int T){
        return bit1.query(T) + bit2.query(T) + bit3.query(T + 1, n) + con;
    };

    deque<int> dq;
    vector<ll> ans(q + 1);
    for(int i = 1; i <= n; i++){
        while(!dq.empty() && a[dq.back()] <= a[i]){
            remove(dq.back());
            dq.pob;
        }
        bit1.off();
        pr[i] = dq.empty() ? -1 : dq.back();
        add(i);
        dq.eb(i);
        con += a[i];

        /*cerr << "test " << i << " " << con << "\n";
        printv(dq, cerr);
        for(int i = 1; i <= n; i++) cerr << bit1.query(i) << " ";
        cerr << "\n";
        for(int i = 1; i <= n; i++) cerr << bit2.query(i) << " ";
        cerr << "\n";
        for(int i = 1; i <= n; i++) cerr << bit3.query(i) << " ";
        cerr << "\n";*/
        
        for(auto j : qry[i]){
            ll tmp = query(j.F);
            if(j.S > 0) ans[j.S] += tmp;
            else ans[-j.S] -= tmp;
        }
    }

    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";

    return 0;
}

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

ho_t5.cpp: In member function 'void BIT::modify(int, ll)':
ho_t5.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(; x < bit.size(); x += lowbit(x)) bit[x] += v;
      |               ~~^~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80