oj.uz

Submission #333414

# Submission time Handle Problem Language Result Execution time Memory
333414 2020-12-05T21:54:46 Z errorgorn Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 230 ms 9068 KB 
#include <bits/stdc++.h>
using namespace std;

int n,q,k;
int arr[100005];
set<int> s;

long long fen[100005];
void update(int i,int j){
    while (i<100005){
        fen[i]+=j;
        i+=i&-i;
    }
}

long long query(int i){
    long long res=0;
    while (i){
        res+=fen[i];
        i-=i&-i;
    }
    return res;
}

long long query(int i,int j){
    return query(j)-query(i-1);
}

int main(){
    scanf("%d%d%d",&n,&q,&k);
    
    for (int x=1;x<=n;x++){
        scanf("%d",&arr[x]);
        if (arr[x]){
            update(x,arr[x]);
            s.insert(x);
        }
    }
    
    int a,b;
    while (q--){
        scanf("%d",&a);
        if (a==2){
            scanf("%d%d",&a,&b);
            if (k==1) continue;
            for (set<int>::iterator it=s.lower_bound(a);it!=s.end() && *it<=b;){
                update(*it,arr[*it]/k-arr[*it]);
                arr[*it]/=k;
                if (arr[*it]==0){
                    it++;
                    s.erase(prev(it));
                }
                else{
                    it++;
                }
            }
        }
        else if (a==1){
            scanf("%d%d",&a,&b);
            update(a,b-arr[a]);
            arr[a]=b;
            s.insert(a);
        }
        else{
            scanf("%d%d",&a,&b);
            printf("%lld\n",query(a,b));
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |     scanf("%d%d%d",&n,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |         scanf("%d",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~
sterilizing.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 4716 KB Output is correct
2 Correct 63 ms 3692 KB Output is correct
3 Correct 65 ms 6252 KB Output is correct
4 Correct 91 ms 7532 KB Output is correct
5 Correct 97 ms 7660 KB Output is correct
6 Correct 98 ms 7660 KB Output is correct
7 Correct 97 ms 7660 KB Output is correct
8 Correct 106 ms 7660 KB Output is correct
9 Correct 96 ms 7660 KB Output is correct
10 Correct 95 ms 7768 KB Output is correct
11 Correct 100 ms 7788 KB Output is correct
12 Correct 96 ms 7660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1004 KB Output is correct
2 Correct 19 ms 2156 KB Output is correct
3 Correct 23 ms 2284 KB Output is correct
4 Correct 52 ms 2284 KB Output is correct
5 Correct 82 ms 5356 KB Output is correct
6 Correct 71 ms 5356 KB Output is correct
7 Correct 76 ms 6124 KB Output is correct
8 Correct 74 ms 5304 KB Output is correct
9 Correct 67 ms 5228 KB Output is correct
10 Correct 73 ms 5228 KB Output is correct
11 Correct 67 ms 5100 KB Output is correct
12 Correct 65 ms 5100 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4588 KB Output is correct
2 Correct 84 ms 4588 KB Output is correct
3 Correct 106 ms 4204 KB Output is correct
4 Correct 92 ms 3564 KB Output is correct
5 Correct 135 ms 8300 KB Output is correct
6 Correct 150 ms 9068 KB Output is correct
7 Correct 132 ms 8940 KB Output is correct
8 Correct 178 ms 8940 KB Output is correct
9 Correct 159 ms 8812 KB Output is correct
10 Correct 177 ms 8812 KB Output is correct
11 Correct 139 ms 8812 KB Output is correct
12 Correct 230 ms 8812 KB Output is correct