oj.uz

Submission #362562

# Submission time Handle Problem Language Result Execution time Memory
362562 2021-02-03T16:33:05 Z denkendoemeer Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 887 ms 10544 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,v[100005];
set<int>st;
struct ain
{
    ll aint[270000];
    void update(int nod,int st,int dr,int poz,int val)
    {
        if (poz<st || poz>dr)
            return ;
        if (st==dr){
            aint[nod]=val;
            return ;
        }
        int mij=(st+dr)/2;
        update(nod*2,st,mij,poz,val);
        update(nod*2+1,mij+1,dr,poz,val);
        aint[nod]=aint[nod*2]+aint[nod*2+1];
    }
    ll query(int nod,int st,int dr,int l,int r)
    {
        if (dr<l || r<st)
            return 0;
        if (l<=st && dr<=r)
            return aint[nod];
        int mij=(st+dr)/2;
        return query(nod*2,st,mij,l,r)+query(nod*2+1,mij+1,dr,l,r);
    }
}ai;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int q,k,i;
    scanf("%d%d%d",&n,&q,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        ai.update(1,1,n,i,v[i]);
        if (v[i])
            st.insert(i);
    }
    for(i=1;i<=q;i++){
        int tip,x,y;
        scanf("%d%d%d",&tip,&x,&y);
        if (tip==1){
            v[x]=y;
            ai.update(1,1,n,x,v[x]);
            if (v[x])
                st.insert(x);
        }
        if (tip==2){
            if (k==1)
                continue;
            auto l=st.lower_bound(x);
            auto r=st.upper_bound(y);
            vector<int>aux;
            while(l!=r){
                int val=*l;
                l++;
                v[val]/=k;
                ai.update(1,1,n,val,v[val]);
                if (v[val]==0)
                    aux.push_back(val);
            }
            for(auto it:aux)
                st.erase(it);
        }
        if (tip==3)
            printf("%lld\n",ai.query(1,1,n,x,y));
    }
return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d",&n,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
sterilizing.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         scanf("%d%d%d",&tip,&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 9 ms 492 KB Output is correct
5 Correct 11 ms 620 KB Output is correct
6 Correct 9 ms 620 KB Output is correct
7 Correct 11 ms 620 KB Output is correct
8 Correct 10 ms 620 KB Output is correct
9 Correct 13 ms 620 KB Output is correct
10 Correct 10 ms 620 KB Output is correct
11 Correct 10 ms 620 KB Output is correct
12 Correct 10 ms 620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 6252 KB Output is correct
2 Correct 87 ms 5100 KB Output is correct
3 Correct 91 ms 8300 KB Output is correct
4 Correct 121 ms 9964 KB Output is correct
5 Correct 144 ms 10348 KB Output is correct
6 Correct 140 ms 10348 KB Output is correct
7 Correct 149 ms 10476 KB Output is correct
8 Correct 138 ms 10348 KB Output is correct
9 Correct 133 ms 10220 KB Output is correct
10 Correct 136 ms 10220 KB Output is correct
11 Correct 132 ms 10220 KB Output is correct
12 Correct 141 ms 10220 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1132 KB Output is correct
2 Correct 33 ms 2924 KB Output is correct
3 Correct 40 ms 3180 KB Output is correct
4 Correct 69 ms 2796 KB Output is correct
5 Correct 130 ms 6764 KB Output is correct
6 Correct 124 ms 6832 KB Output is correct
7 Correct 113 ms 7148 KB Output is correct
8 Correct 120 ms 6636 KB Output is correct
9 Correct 115 ms 6700 KB Output is correct
10 Correct 114 ms 6568 KB Output is correct
11 Correct 113 ms 6572 KB Output is correct
12 Correct 111 ms 6572 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 5868 KB Output is correct
2 Correct 220 ms 5996 KB Output is correct
3 Correct 373 ms 5100 KB Output is correct
4 Correct 242 ms 4588 KB Output is correct
5 Correct 403 ms 10448 KB Output is correct
6 Correct 483 ms 10220 KB Output is correct
7 Correct 383 ms 10220 KB Output is correct
8 Correct 634 ms 10320 KB Output is correct
9 Correct 516 ms 10328 KB Output is correct
10 Correct 616 ms 10264 KB Output is correct
11 Correct 421 ms 10216 KB Output is correct
12 Correct 887 ms 10544 KB Output is correct