oj.uz

Submission #329215

# Submission time Handle Problem Language Result Execution time Memory
329215 2020-11-19T22:29:02 Z iliccmarko Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 259 ms 4584 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
using namespace std;
int n, q, k;
const int N = 1e5 + 5;
int sum[4*N];
vector<int> a(N);

int get_sum(int node, int l, int r, int i, int j)
{
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r) return sum[node];
    int mid = (i+j)/2;
    return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}

void update(int node, int l, int r, int pos, int x)
{
    if(l==r)
    {
        sum[node] = x;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid)
        update(node*2+2, mid+1, r, pos, x);
    else
        update(node*2+1, l, mid, pos, x);
    sum[node] = sum[node*2+1] + sum[node*2+2];
}

int build_sum(int node, int l, int r)
{
    if(l==r)
    {
       return sum[node] = a[l];
    }
    int mid = (l+r)/2;
    return sum[node] = build_sum(node*2+1, l, mid) + build_sum(node*2+2, mid+1, r);
}


int main()
{
    ios
    cin>>n>>q>>k;
    for(int i = 0;i<n;i++)
        cin>>a[i];
    //cout<<11111<<endl;
    set<int> alive;
    for(int i = 0;i<n;i++)
        if(a[i])
        alive.insert(i);
    build_sum(0, 0, n-1);
    //cout<<2222<<endl;
    while(q--)
    {
        int s, t, u;
        cin>>s>>t>>u;
        t--;
        u--;
        if(s==1)
        {
            // a-ti tanjir na b
            u++;
            //cout<<a[t]<<" "<<u<<endl;
            if(!a[t]&&u)
            alive.insert(t);
            if(a[t]&&!u)
                alive.erase(t);
            a[t] = u;
            update(0, 0, n-1, t, u);
        }
        else if(s==2)
        {
            // sprej
            if(k==1) continue;
            vector<int> s;
            for(int x : alive)
            {
                //cout<<x<<" ";
                //cout<<x<<" ";
                //line
                //cout<<x<<" "<<a[x]<<endl;
                if(x<t||x>u) continue;
                //cout<<x<<" "<<a[x]<<endl;
                a[x] /= k;
                if(!a[x])
                    s.pb(x);
                update(0, 0, n-1, x, a[x]);
            }
            for(int x : s)
                alive.erase(x);
            //cout<<endl;
            //cout<<endl;
        }
        else{
            // ispisi sumu od l do r
            //cout<<u<<" "<<t<<endl;
            cout<<get_sum(0, t, u, 0, n-1);
                cout<<endl;
        }
    }




    return 0;
}
/*
5 10 3
27 27 27 27 27
2 2 4
2 1 5
2 3 3
2 3 5
1 4 9
1 5 9
3 1 5
3 1 5
3 1 5
3 1 5
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 3948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1004 KB Output is correct
2 Correct 26 ms 2284 KB Output is correct
3 Correct 30 ms 2412 KB Output is correct
4 Correct 66 ms 1700 KB Output is correct
5 Correct 97 ms 4332 KB Output is correct
6 Correct 96 ms 4256 KB Output is correct
7 Correct 83 ms 4332 KB Output is correct
8 Correct 111 ms 4204 KB Output is correct
9 Correct 84 ms 4460 KB Output is correct
10 Correct 84 ms 4460 KB Output is correct
11 Correct 86 ms 4584 KB Output is correct
12 Correct 83 ms 4460 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 3948 KB Output isn't correct
2 Halted 0 ms 0 KB -