oj.uz

Submission #620415

# Submission time Handle Problem Language Result Execution time Memory
620415 2022-08-03T05:36:46 Z 조영욱(#8520) Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2415 ms 6124 KB 
#include <bits/stdc++.h>
using namespace std;

int n,q,k;
typedef pair<int,int> P;
const int sz=131072;
P seg[sz*2];
long long seg1[sz*2];

P get(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return P(0,-1);
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return max(get(l,r,node*2,nodel,mid),get(l,r,node*2+1,mid+1,noder));
}

long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg1[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int i,int x) {
    int pos=i;
    i+=sz;
    seg[i]=P(x,i-sz);
    while (i>1) {
        i/=2;
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }
    i=pos+sz;
    seg1[i]=x;
    while (i>1) {
        i/=2;
        seg1[i]=seg1[i*2]+seg1[i*2+1];
    }
}

int main(void) {
    scanf("%d %d %d",&n,&q,&k);
    for(int i=0;i<n;i++) {
        int x;
        scanf("%d",&x);
        update(i,x);
    }
    for(int i=0;i<q;i++) {
        int t,a,b;
        scanf("%d %d %d",&t,&a,&b);
        if (t==1) {
            a--;
            update(a,b);
        }
        if (t==2) {
            if (k==1) {
                continue;
            }
            vector<P> save;
            a--;
            b--;
            while (1) {
                P got=get(a,b);
//printf("%d %d\n",got.first,got.second);
                if (got.first==0) {
                    break;
                }
                save.push_back(got);
                update(got.second,0);
            }
            for(int j=0;j<save.size();j++) {
                update(save[j].second,save[j].first/k);
            }
        }
        if (t==3) {
            a--;
            b--;
            printf("%lld\n",sum(a,b));
        }
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(int j=0;j<save.size();j++) {
      |                         ~^~~~~~~~~~~~
sterilizing.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d %d",&n,&q,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
sterilizing.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d %d",&t,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 8 ms 492 KB Output is correct
4 Correct 26 ms 612 KB Output is correct
5 Correct 28 ms 572 KB Output is correct
6 Correct 24 ms 596 KB Output is correct
7 Correct 31 ms 580 KB Output is correct
8 Correct 25 ms 596 KB Output is correct
9 Correct 31 ms 584 KB Output is correct
10 Correct 22 ms 596 KB Output is correct
11 Correct 20 ms 604 KB Output is correct
12 Correct 25 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3052 KB Output is correct
2 Correct 50 ms 2492 KB Output is correct
3 Correct 49 ms 3812 KB Output is correct
4 Correct 62 ms 4556 KB Output is correct
5 Correct 72 ms 4652 KB Output is correct
6 Correct 75 ms 4652 KB Output is correct
7 Correct 79 ms 4712 KB Output is correct
8 Correct 80 ms 4668 KB Output is correct
9 Correct 71 ms 4624 KB Output is correct
10 Correct 83 ms 4704 KB Output is correct
11 Correct 68 ms 4664 KB Output is correct
12 Correct 71 ms 4708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1064 KB Output is correct
2 Correct 30 ms 2112 KB Output is correct
3 Correct 34 ms 2252 KB Output is correct
4 Correct 71 ms 2004 KB Output is correct
5 Correct 116 ms 4424 KB Output is correct
6 Correct 161 ms 4364 KB Output is correct
7 Correct 65 ms 4428 KB Output is correct
8 Correct 108 ms 4440 KB Output is correct
9 Correct 113 ms 4432 KB Output is correct
10 Correct 110 ms 4436 KB Output is correct
11 Correct 133 ms 4440 KB Output is correct
12 Correct 136 ms 4432 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 4132 KB Output is correct
2 Correct 466 ms 3172 KB Output is correct
3 Correct 1068 ms 3188 KB Output is correct
4 Correct 637 ms 2548 KB Output is correct
5 Correct 910 ms 5144 KB Output is correct
6 Correct 994 ms 4956 KB Output is correct
7 Correct 767 ms 5688 KB Output is correct
8 Correct 1451 ms 5856 KB Output is correct
9 Correct 1358 ms 5808 KB Output is correct
10 Correct 1601 ms 6124 KB Output is correct
11 Correct 962 ms 5856 KB Output is correct
12 Correct 2415 ms 6084 KB Output is correct