oj.uz

Submission #78121

# Submission time Handle Problem Language Result Execution time Memory
78121 2018-10-02T13:50:39 Z nxteru Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 250 ms 12620 KB 
#include <iostream>
#include <algorithm>
#include <set>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n,q,k,p[100005],bit[100005];
set<int>o;
void add(int a,ll x){
    while(a<=n){
        bit[a]+=x;
        a+=(a&-a);
    }
}
ll sum(int a){
    ll res=0;
    while(a>0){
        res+=bit[a];
        a-=(a&-a);
    }
    return res;
}
int main(void){
    scanf("%lld%lld%lld",&n,&q,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",p+i);
        add(i,p[i]);
        if(p[i]>0)o.insert(i);
    }
    while(q){
        ll s,a,b;
        scanf("%lld%lld%lld",&s,&a,&b);
        if(s==1){
            add(a,b-p[a]);
            p[a]=b;
            o.insert(a);
        }
        if(s==2&&k!=1){
            auto it=o.lower_bound(a);
            while(it!=o.end()&&*it<=b){
                add(*it,-p[*it]+p[*it]/k);
                p[*it]/=k;
                if(p[*it]==0){
                    auto itr=it;
                    it++;
                    o.erase(itr);
                }else it++;
            }
        }
        if(s==3){
            printf("%lld\n",sum(b)-sum(a-1));
        }
        q--;
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",p+i);
         ~~~~~^~~~~~~~~~~~
sterilizing.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&s,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 404 KB Output is correct
3 Correct 3 ms 736 KB Output is correct
4 Correct 8 ms 736 KB Output is correct
5 Correct 8 ms 960 KB Output is correct
6 Correct 9 ms 1044 KB Output is correct
7 Correct 10 ms 1240 KB Output is correct
8 Correct 7 ms 1240 KB Output is correct
9 Correct 7 ms 1256 KB Output is correct
10 Correct 7 ms 1324 KB Output is correct
11 Correct 8 ms 1360 KB Output is correct
12 Correct 6 ms 1424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6216 KB Output is correct
2 Correct 69 ms 6216 KB Output is correct
3 Correct 74 ms 8788 KB Output is correct
4 Correct 106 ms 10200 KB Output is correct
5 Correct 123 ms 10348 KB Output is correct
6 Correct 111 ms 10580 KB Output is correct
7 Correct 117 ms 10580 KB Output is correct
8 Correct 111 ms 10580 KB Output is correct
9 Correct 103 ms 10580 KB Output is correct
10 Correct 147 ms 10580 KB Output is correct
11 Correct 119 ms 10580 KB Output is correct
12 Correct 138 ms 10580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10580 KB Output is correct
2 Correct 21 ms 10580 KB Output is correct
3 Correct 24 ms 10580 KB Output is correct
4 Correct 50 ms 10580 KB Output is correct
5 Correct 76 ms 10580 KB Output is correct
6 Correct 75 ms 10580 KB Output is correct
7 Correct 78 ms 10580 KB Output is correct
8 Correct 75 ms 10580 KB Output is correct
9 Correct 68 ms 10580 KB Output is correct
10 Correct 70 ms 10580 KB Output is correct
11 Correct 70 ms 10580 KB Output is correct
12 Correct 68 ms 10580 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10580 KB Output is correct
2 Correct 104 ms 10580 KB Output is correct
3 Correct 116 ms 10580 KB Output is correct
4 Correct 100 ms 10580 KB Output is correct
5 Correct 183 ms 12520 KB Output is correct
6 Correct 200 ms 12528 KB Output is correct
7 Correct 151 ms 12528 KB Output is correct
8 Correct 208 ms 12528 KB Output is correct
9 Correct 175 ms 12528 KB Output is correct
10 Correct 197 ms 12528 KB Output is correct
11 Correct 156 ms 12620 KB Output is correct
12 Correct 250 ms 12620 KB Output is correct