제출 #528923

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

sterilizing

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
#define MAXN 100010
using namespace std;

ll seg[4*MAXN];
set<int> indeksi;
void update(int node, int l, int r, int idx, int val){
    if(l == r){
        seg[node] = val;
        //cout << "idx: " << l << ", val: " << seg[node] << ", node: " << node << endl;
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid) update(2*node, l, mid, idx, val);
    else update(2*node+1, mid+1, r, idx, val);
    seg[node] = seg[2*node] + seg[2*node+1];
}
vector<int> rem;
void update2(int node, int l, int r, int idx, int k){
    if(l == r){
            //cout << "indeks: " << l << ": " << seg[node] << endl;
        seg[node] /= k;
        if(seg[node] == 0){ /*cout << "brise se indeks: " << l << ", jer je seg[node] = " << seg[node] << ", node: " << node << endl;*/ rem.push_back(idx);}
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid) update2(2*node, l, mid, idx, k);
    else update2(2*node+1, mid+1, r, idx, k);
    seg[node] = seg[2*node] + seg[2*node+1];
}
ll query(int node, int l, int r, int L, int R){
    if(L <= l && r <= R)
        return seg[node];
    int mid = (l+r)/2;
    ll sum = 0;
    if(L <= mid) sum += query(2*node, l, mid, L, R);
    if(R > mid) sum += query(2*node+1, mid+1, r, L, R);
    return sum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q, k;
    cin >> n >> q >> k;
    for(int i = 0; i < n; i++){
        int t; cin >> t;
        update(1, 1, MAXN, i+1, t);
    }
    for(int i = 1; i <= n; i++) indeksi.insert(i);
    for(int i = 0; i < q; i++){
        int s, l, r;
        cin >> s >> l >> r;
        if(s == 1){
            update(1, 1, MAXN, l, r);
            indeksi.insert(l);
                /*for(auto x : indeksi) cout << x << ", ";
                cout << endl;*/
        }
        else if(s == 2){
            if(k != 2){
                //cout << "START" << endl;
                for(auto it = indeksi.lower_bound(l); it != indeksi.end() && !indeksi.empty() && *it <= r; it++){
                //    cout << *it << ": ";
                    update2(1, 1, MAXN, *it, k);
                //    cout << "done" << endl;
                }
                //cout << "MID" << endl;
                for(auto x : rem){
                    indeksi.erase(x);
                } rem.clear();
                /*for(auto x : indeksi) cout << x << ", ";
                cout << endl;*/
                //cout << "END" << endl;
            }
        }
        else{
            cout << query(1, 1, MAXN, l, r) << endl;
        }
    }
    return 0;
}

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