제출 #534576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534576		Danilo21	Sterilizing Spray (JOI15_sterilizing)	C++14	0 / 100	5035 ms	66212 KiB

sterilizing

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) __builtin_popcountll(a)
#define bithigh(a) 63-__builtin_clzll(a)
#define lg bithigh
ll highpow(ll a) { return 1LL << (ll)lg(a); }

using namespace std;

template<class T>
class segtree{
private:
    int n;
    vector<T> tree, lazy;
    vector<bool> f;
    void init(int n){
        this->n = n;
        if (highpow(n)^n) this->n = 2*highpow(n);
        this->tree = vector<T>(2 * this->n, T());
        this->lazy = vector<T>(2 * this->n, T());
        this->f = vector<bool>(2 * this->n, 0);
    }
    T build(int s, int l, int r, auto* arr){
        if (l == r) return this->tree[s] = T(arr[l]);

        int m = (l + r) / 2;
        T a = build(2*s, l, m, arr);
        T b = build(2*s+1, m+1, r, arr);
        return this->tree[s] = T::op(a, b);
    }
    T update(int s, int l, int r, int ul, int ur, T x){
        eval_lazy(s, l, r);
        if (l > ur || r < ul) return this->tree[s];
        if (l >= ul && r <= ur){
            this->lazy[s].up(x);
            this->f[s] = 1;
            eval_lazy(s, l, r);
            return this->tree[s];
        }

        int m = (l + r) / 2;
        T a = update(2*s, l, m, ul, ur, x);
        T b = update(2*s+1, m+1, r, ul, ur, x);
        return this->tree[s] = T::op(a, b);
    }
    T query(int s, int l, int r, int ql, int qr) {
        eval_lazy(s, l, r);
        if (l > qr || r < ql) return T::null_v();
        if (l >= ql && r <= qr) return this->tree[s];

        int m = (l + r) / 2;
        T a = query(2*s, l, m, ql, qr);
        T b = query(2*s+1, m+1, r, ql, qr);
        return T::op(a, b);
    }
    void eval_lazy(int s, int l, int r){
        if (!this->f[s]) return;
        this->tree[s].lazy_op(this->lazy[s], r-l+1);
        if (l^r){
            this->lazy[2*s].up(this->lazy[s]);
            this->f[2*s] = 1;
            this->lazy[2*s+1].up(this->lazy[s]);
            this->f[2*s+1] = 1;
        }
        this->lazy[s] = T();
        this->f[s] = 0;
    }
public:
    segtree(int n = 0){ init(n); }
    segtree(int n, auto* arr){ init(n); build(1, 0, this->n - 1, arr); }

    void update(int l, int r, auto x) { update(1, 0, this->n-1, l, r, T(x)); }
    auto query(int l, int r) { if (l>r) return T::null_v().val; return query(1, 0, this->n-1, l, r).val; }

    void logTree() const { for (int i = 1; i < 2*this->n; i++) this->tree[i].log(); cerr << endl; }
    void logLazy() const { for (int i = 1; i < 2*this->n; i++) this->lazy[i].log(); cerr << endl; }
};
class sum_t{
public:
    ll val;

    sum_t(ll val = 0){ this->val = val; }
    static sum_t null_v(){ return sum_t(0); }

    static sum_t op(const sum_t& a, const sum_t& b){ return a + b; }
    // This is currently on set mode but it can be on add.
    sum_t up(const sum_t& a){ return *this = a; }
    void lazy_op(const sum_t& a, int l){ up(sum_t(a.val * l)); }

    sum_t operator =(const sum_t& a){ this->val = a.val; return *this; }
    sum_t operator +=(const sum_t& a) { this->val += a.val; return *this; }
    sum_t operator -=(const sum_t& a) { this->val -= a.val; return *this; }
    sum_t operator +(const sum_t& a) const { return sum_t(this->val + a.val); }
    sum_t operator -(const sum_t& a) const { return sum_t(this->val - a.val); }
    bool operator ==(const sum_t& a) const { return this->val == a.val; }
    bool operator !=(const sum_t& a) const { return this->val != a.val; }

    void Print() const { cout << this->val << sp; }
    void log() const { cerr << this->val << sp; }
};
class set_t{
public:
    set<int> val;

    set_t(ll val = -1){ if (~val) this->val.insert(val); }
    static set_t null_v() { return set_t(); }

    static set_t op(const set_t& a, const set_t& b){
        set_t s;
        s.val = a.val;
        for (int x : b.val) s.val.insert(x);
        return s;
    }
    set_t up(const set_t& a){ return *this = a; }
    void lazy_op(const set_t& a, int l){ up(a); }

    set_t operator=(const set_t& a){ this->val = a.val; return *this; }
};

const ll LINF = 4e18;
const int mxN = 2e5+10, INF = 2e9, mod = (1 ? 1e9+7 : 998244353);
ll n, q, m, a[mxN];
segtree<sum_t>* st1;
segtree<set_t>* st2;

void Solve(){

    cin >> n >> q >> m;
    memset(a, -1, sizeof(a));
    for (int i = 0; i < n; i++) if (a[i]) a[i] = i;
    st2 = new segtree<set_t>(n, a);
    memset(a, 0, sizeof(a));
    for (int i = 0; i < n; i++)
        cin >> a[i];
    st1 = new segtree<sum_t>(n, a);
    while (q--){
        ri(t);
        if (t == 1){
            ri(i); i--; ri(x);
            st1->update(i, i, x);
            if (!x) st2->update(i, i, -1);
        }
        if (t == 2){
            ri(l); ri(r);
            l--; r--;
            set<int> s = st2->query(l, r);
            for (int i : s){
                int x = st1->query(i, i);
                st1->update(i, i, x/m);
                if (!(x/m)) st2->update(i, i, -1);
            }
        }
        if (t == 3){
            ri(l); ri(r);
            l--; r--;
            cout << st1->query(l, r) << en;
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

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

sterilizing.cpp: In function 'long long int highpow(long long int)':
sterilizing.cpp:26:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   26 | #define bithigh(a) 63-__builtin_clzll(a)
      |                      ^
sterilizing.cpp:27:12: note: in expansion of macro 'bithigh'
   27 | #define lg bithigh
      |            ^~~~~~~
sterilizing.cpp:28:38: note: in expansion of macro 'lg'
   28 | ll highpow(ll a) { return 1LL << (ll)lg(a); }
      |                                      ^~
sterilizing.cpp: At global scope:
sterilizing.cpp:45:34: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   45 |     T build(int s, int l, int r, auto* arr){
      |                                  ^~~~
sterilizing.cpp:92:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   92 |     segtree(int n, auto* arr){ init(n); build(1, 0, this->n - 1, arr); }
      |                    ^~~~
sterilizing.cpp:94:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   94 |     void update(int l, int r, auto x) { update(1, 0, this->n-1, l, r, T(x)); }
      |                               ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75