oj.uz

Submission #219263

# Submission time Handle Problem Language Result Execution time Memory
219263 2020-04-04T21:07:03 Z MKopchev Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1485 ms 9336 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,q,k,inp[nmax];

long long fenwick[nmax];
void update(int pos,int val)
{
    while(pos<=n)
    {
        fenwick[pos]+=val;
        pos=pos+(pos&(-pos));
    }
}
long long sum(int pos)
{
    long long ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}
long long query(int l,int r)
{
    return sum(r)-sum(l-1);
}

set<int> non_zero;
void make(int pos,int val)
{
    //cout<<"make "<<pos<<" "<<val<<endl;

    if(inp[pos])non_zero.erase(pos);
    update(pos,-inp[pos]);

    inp[pos]=val;
    if(inp[pos])non_zero.insert(pos);
    update(pos,inp[pos]);
}

int main()
{
    scanf("%i%i%i",&n,&q,&k);

    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);

        int was=inp[i];
        inp[i]=0;

        make(i,was);

        if(inp[i])non_zero.insert(i);
    }

    int type,l,r;
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i%i",&type,&l,&r);
        if(type==1)
        {
            make(l,r);
        }
        if(type==2&&k!=1)
        {
            int lst_used=l-1;
            while(1)
            {
                set<int>::iterator it=non_zero.upper_bound(lst_used);
                if(it==non_zero.end())break;

                int current=*it;
                if(current>r)break;

                make(current,inp[current]/k);
                lst_used=current;
            }
        }
        if(type==3)
        {
            printf("%lld\n",query(l,r));
        }
        /*
        for(int j=1;j<=n;j++)
            cout<<query(j,j)<<" ";cout<<endl;
        cout<<"---"<<endl;
        */
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&q,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sterilizing.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
sterilizing.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&type,&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 9 ms 512 KB Output is correct
4 Correct 21 ms 512 KB Output is correct
5 Correct 22 ms 640 KB Output is correct
6 Correct 15 ms 768 KB Output is correct
7 Correct 19 ms 768 KB Output is correct
8 Correct 19 ms 640 KB Output is correct
9 Correct 24 ms 640 KB Output is correct
10 Correct 18 ms 640 KB Output is correct
11 Correct 19 ms 640 KB Output is correct
12 Correct 21 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5496 KB Output is correct
2 Correct 71 ms 4344 KB Output is correct
3 Correct 92 ms 7032 KB Output is correct
4 Correct 115 ms 8568 KB Output is correct
5 Correct 123 ms 9080 KB Output is correct
6 Correct 135 ms 9336 KB Output is correct
7 Correct 133 ms 9080 KB Output is correct
8 Correct 123 ms 9080 KB Output is correct
9 Correct 127 ms 9080 KB Output is correct
10 Correct 133 ms 8956 KB Output is correct
11 Correct 122 ms 8952 KB Output is correct
12 Correct 125 ms 8952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1024 KB Output is correct
2 Correct 25 ms 2176 KB Output is correct
3 Correct 31 ms 2432 KB Output is correct
4 Correct 51 ms 2552 KB Output is correct
5 Correct 82 ms 5368 KB Output is correct
6 Correct 80 ms 5368 KB Output is correct
7 Correct 78 ms 5496 KB Output is correct
8 Correct 85 ms 5368 KB Output is correct
9 Correct 83 ms 5372 KB Output is correct
10 Correct 85 ms 5112 KB Output is correct
11 Correct 88 ms 5240 KB Output is correct
12 Correct 79 ms 5112 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 5112 KB Output is correct
2 Correct 312 ms 5368 KB Output is correct
3 Correct 631 ms 4396 KB Output is correct
4 Correct 373 ms 4192 KB Output is correct
5 Correct 566 ms 8952 KB Output is correct
6 Correct 684 ms 9208 KB Output is correct
7 Correct 514 ms 8924 KB Output is correct
8 Correct 965 ms 8952 KB Output is correct
9 Correct 779 ms 8824 KB Output is correct
10 Correct 1000 ms 8824 KB Output is correct
11 Correct 614 ms 8952 KB Output is correct
12 Correct 1485 ms 8824 KB Output is correct