oj.uz

Submission #83299

# Submission time Handle Problem Language Result Execution time Memory
83299 2018-11-06T18:51:03 Z Bodo171 Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 39768 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;
            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 6 ms 380 KB Output is correct
2 Correct 5 ms 548 KB Output is correct
3 Correct 4 ms 752 KB Output is correct
4 Correct 8 ms 772 KB Output is correct
5 Correct 13 ms 952 KB Output is correct
6 Correct 7 ms 1128 KB Output is correct
7 Correct 8 ms 1196 KB Output is correct
8 Correct 8 ms 1264 KB Output is correct
9 Correct 9 ms 1332 KB Output is correct
10 Correct 8 ms 1400 KB Output is correct
11 Correct 8 ms 1484 KB Output is correct
12 Correct 8 ms 1552 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5062 ms 6012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6012 KB Output is correct
2 Correct 58 ms 6012 KB Output is correct
3 Correct 56 ms 6388 KB Output is correct
4 Correct 117 ms 6440 KB Output is correct
5 Correct 175 ms 12464 KB Output is correct
6 Correct 167 ms 13748 KB Output is correct
7 Execution timed out 5092 ms 14676 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 14676 KB Output is correct
2 Correct 148 ms 15024 KB Output is correct
3 Correct 176 ms 15692 KB Output is correct
4 Correct 163 ms 16844 KB Output is correct
5 Correct 231 ms 23304 KB Output is correct
6 Correct 264 ms 25568 KB Output is correct
7 Correct 251 ms 27988 KB Output is correct
8 Correct 315 ms 30620 KB Output is correct
9 Correct 260 ms 32852 KB Output is correct
10 Correct 283 ms 35224 KB Output is correct
11 Correct 245 ms 37468 KB Output is correct
12 Correct 327 ms 39768 KB Output is correct