Submission #549455

#	Time	Username	Problem	Language	Result	Execution time	Memory
549455		skyvn97	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	3497 ms	109004 KiB

sterilizing

#include<bits/stdc++.h>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
class SegmentTree {
    private:
    int n;
    vector<set<int> > nonZero;
    vector<long long> sum;
    void assign(int i,int l,int r,int x,int v) {
        if (v==0) nonZero[i].erase(x);
        else nonZero[i].insert(x);
        if (l==r) {
            sum[i]=v;
            return;
        }
        int m=(l+r)>>1;
        if (x>m) assign(2*i+1,m+1,r,x,v);
        else assign(2*i,l,m,x,v);
        sum[i]=sum[2*i]+sum[2*i+1];
    }
    long long getSum(int i,int l,int r,int u,int v) const {
        if (l>v || r<u || l>r || v<u) return (0);
        if (u<=l && r<=v) return (sum[i]);
        int m=(l+r)>>1;
        long long L=getSum(2*i,l,m,u,v);
        long long R=getSum(2*i+1,m+1,r,u,v);
        return (L+R);
    }
    void getNonZero(vector<int> &res,int i,int l,int r,int u,int v) {
        if (l>v || r<u || l>r || v<u) return;
        if (u<=l && r<=v) {
            FORE(it,nonZero[i]) res.push_back(*it);
            return;
        }
        int m=(l+r)>>1;
        getNonZero(res,2*i,l,m,u,v);
        getNonZero(res,2*i+1,m+1,r,u,v);
    }
    public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int n) {
        this->n=n;
        nonZero.assign(4*n+7,set<int>());
        sum.assign(4*n+7,0);
    }
    void assign(int x,int v) {
        assign(1,1,n,x,v);
    }
    long long getSum(int l,int r) const {
        return (getSum(1,1,n,l,r));
    }
    void getNonZero(vector<int> &v,int l,int  r) {
        v.clear();
        getNonZero(v,1,1,n,l,r);
    }
};
int a[MAX],n,q,k;
void init(void) {
    scanf("%d%d%d",&n,&q,&k);
    FOR(i,1,n) scanf("%d",&a[i]);
}
void process(void) {
    SegmentTree myit(n);
    FOR(i,1,n) myit.assign(i,a[i]);
    REP(love,q) {
        int t,u,v;
        scanf("%d%d%d",&t,&u,&v);
        if (t==1) {
            a[u]=v;
            myit.assign(u,a[u]);
        }
        if (t==2 && k>1) {
            vector<int> id;
            myit.getNonZero(id,u,v);
            FORE(it,id) {
                a[*it]/=k;
                myit.assign(*it,a[*it]);
            }
        }
        if (t==3) cout<<myit.getSum(u,v)<<"\n";
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'void init()':
sterilizing.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d%d",&n,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:65:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     FOR(i,1,n) scanf("%d",&a[i]);
      |                ~~~~~^~~~~~~~~~~~
sterilizing.cpp: In function 'void process()':
sterilizing.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d%d%d",&t,&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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