oj.uz

Submission #549455

# Submission time Handle Problem Language Result Execution time Memory
549455 2022-04-15T20:20:59 Z skyvn97 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 3497 ms 109004 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 10 ms 1748 KB Output is correct
4 Correct 24 ms 1444 KB Output is correct
5 Correct 30 ms 2852 KB Output is correct
6 Correct 30 ms 2776 KB Output is correct
7 Correct 32 ms 2772 KB Output is correct
8 Correct 28 ms 2844 KB Output is correct
9 Correct 34 ms 2852 KB Output is correct
10 Correct 26 ms 2772 KB Output is correct
11 Correct 27 ms 2788 KB Output is correct
12 Correct 27 ms 2772 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 51596 KB Output is correct
2 Correct 234 ms 34680 KB Output is correct
3 Correct 459 ms 82200 KB Output is correct
4 Correct 569 ms 106656 KB Output is correct
5 Correct 642 ms 108700 KB Output is correct
6 Correct 633 ms 108508 KB Output is correct
7 Correct 660 ms 108600 KB Output is correct
8 Correct 637 ms 108608 KB Output is correct
9 Correct 624 ms 108584 KB Output is correct
10 Correct 655 ms 108476 KB Output is correct
11 Correct 619 ms 108512 KB Output is correct
12 Correct 619 ms 108360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4260 KB Output is correct
2 Correct 97 ms 27880 KB Output is correct
3 Correct 107 ms 28252 KB Output is correct
4 Correct 139 ms 15884 KB Output is correct
5 Correct 317 ms 65648 KB Output is correct
6 Correct 321 ms 65780 KB Output is correct
7 Correct 454 ms 65744 KB Output is correct
8 Correct 329 ms 65676 KB Output is correct
9 Correct 286 ms 65500 KB Output is correct
10 Correct 283 ms 65500 KB Output is correct
11 Correct 286 ms 65436 KB Output is correct
12 Correct 295 ms 65420 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 53932 KB Output is correct
2 Correct 719 ms 54984 KB Output is correct
3 Correct 1434 ms 46788 KB Output is correct
4 Correct 731 ms 33644 KB Output is correct
5 Correct 1581 ms 108544 KB Output is correct
6 Correct 1894 ms 108688 KB Output is correct
7 Correct 1396 ms 108960 KB Output is correct
8 Correct 2448 ms 108984 KB Output is correct
9 Correct 1945 ms 108568 KB Output is correct
10 Correct 2327 ms 108956 KB Output is correct
11 Correct 1564 ms 108460 KB Output is correct
12 Correct 3497 ms 109004 KB Output is correct