oj.uz

Submission #83300

# Submission time Handle Problem Language Result Execution time Memory
83300 2018-11-06T18:53:16 Z Bodo171 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 331 ms 39640 KB 
#include <iostream>
#include <fstream>
#include <set>
using namespace std;
const int nmax=100005;
set<int> s;
set<int>::iterator it,it1;
long long aib[nmax];
int v[nmax];
int n,i,q,k,tip,val,poz,l,r;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
long long compute(int poz)
{
    long long ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>q>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        update(i,v[i]);
        s.insert(i);
    }
    s.insert(n+1);
    for(i=1;i<=q;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>poz>>val;
            update(poz,-v[poz]);
            v[poz]=val;
            update(poz,v[poz]);
            s.insert(poz);
        }
        if(tip==2)
        {
            cin>>l>>r;
            if(k==1) continue;
            it=s.lower_bound(l);
            while((*it)<=r)
            {
                it1=it;it1++;
                poz=(*it);
                update(poz,-v[poz]);
                v[poz]/=k;
                update(poz,v[poz]);
                if(!v[poz])
                    s.erase(poz);
                it=it1;
            }
        }
        if(tip==3)
        {
            cin>>l>>r;
            cout<<compute(r)-compute(l-1)<<'\n';
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 440 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 7 ms 584 KB Output is correct
5 Correct 12 ms 872 KB Output is correct
6 Correct 7 ms 872 KB Output is correct
7 Correct 8 ms 872 KB Output is correct
8 Correct 12 ms 872 KB Output is correct
9 Correct 9 ms 936 KB Output is correct
10 Correct 9 ms 936 KB Output is correct
11 Correct 8 ms 936 KB Output is correct
12 Correct 8 ms 936 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 4660 KB Output is correct
2 Correct 127 ms 5540 KB Output is correct
3 Correct 170 ms 9572 KB Output is correct
4 Correct 156 ms 12972 KB Output is correct
5 Correct 168 ms 15604 KB Output is correct
6 Correct 187 ms 18092 KB Output is correct
7 Correct 176 ms 20556 KB Output is correct
8 Correct 184 ms 23084 KB Output is correct
9 Correct 207 ms 25328 KB Output is correct
10 Correct 165 ms 27644 KB Output is correct
11 Correct 170 ms 30072 KB Output is correct
12 Correct 171 ms 32368 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 32368 KB Output is correct
2 Correct 39 ms 32368 KB Output is correct
3 Correct 57 ms 32368 KB Output is correct
4 Correct 112 ms 32368 KB Output is correct
5 Correct 168 ms 32368 KB Output is correct
6 Correct 169 ms 32368 KB Output is correct
7 Correct 172 ms 32784 KB Output is correct
8 Correct 156 ms 34080 KB Output is correct
9 Correct 172 ms 35376 KB Output is correct
10 Correct 148 ms 36804 KB Output is correct
11 Correct 153 ms 38000 KB Output is correct
12 Correct 163 ms 39216 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 39216 KB Output is correct
2 Correct 145 ms 39216 KB Output is correct
3 Correct 147 ms 39216 KB Output is correct
4 Correct 155 ms 39216 KB Output is correct
5 Correct 226 ms 39516 KB Output is correct
6 Correct 244 ms 39580 KB Output is correct
7 Correct 227 ms 39580 KB Output is correct
8 Correct 287 ms 39640 KB Output is correct
9 Correct 271 ms 39640 KB Output is correct
10 Correct 277 ms 39640 KB Output is correct
11 Correct 219 ms 39640 KB Output is correct
12 Correct 331 ms 39640 KB Output is correct