oj.uz

Submission #412849

# Submission time Handle Problem Language Result Execution time Memory
412849 2021-05-27T17:00:42 Z iliccmarko Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 843 ms 10836 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;
ll sum[4*N];
vector<ll> a(N);

ll 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];
}

ll 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<ll> alive;
    for(ll i = 0;i<n;i++)
        if(a[i])
        alive.insert(i);
    build_sum(0, 0, n-1);
    //cout<<2222<<endl;
    while(q--)
    {
        ll 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;
            auto w = alive.lower_bound(t);
            while(w!=alive.end())
            {
                if((*w)>u) break;
                int e = *w;
                a[e]/=k;
                if(!a[e]) s.pb(e);
                update(0, 0, n-1, e, a[e]);
                w++;
            }
            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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1100 KB Output is correct
2 Correct 2 ms 1140 KB Output is correct
3 Correct 4 ms 1228 KB Output is correct
4 Correct 10 ms 1228 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 9 ms 1384 KB Output is correct
7 Correct 10 ms 1356 KB Output is correct
8 Correct 11 ms 1396 KB Output is correct
9 Correct 13 ms 1396 KB Output is correct
10 Correct 10 ms 1356 KB Output is correct
11 Correct 10 ms 1388 KB Output is correct
12 Correct 11 ms 1484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6724 KB Output is correct
2 Correct 59 ms 5704 KB Output is correct
3 Correct 65 ms 8716 KB Output is correct
4 Correct 79 ms 10168 KB Output is correct
5 Correct 98 ms 10692 KB Output is correct
6 Correct 92 ms 10748 KB Output is correct
7 Correct 92 ms 10692 KB Output is correct
8 Correct 94 ms 10828 KB Output is correct
9 Correct 90 ms 10552 KB Output is correct
10 Correct 94 ms 10652 KB Output is correct
11 Correct 92 ms 10560 KB Output is correct
12 Correct 92 ms 10552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1868 KB Output is correct
2 Correct 25 ms 3360 KB Output is correct
3 Correct 30 ms 3564 KB Output is correct
4 Correct 62 ms 3404 KB Output is correct
5 Correct 102 ms 6984 KB Output is correct
6 Correct 96 ms 6940 KB Output is correct
7 Correct 86 ms 7060 KB Output is correct
8 Correct 99 ms 6980 KB Output is correct
9 Correct 91 ms 6936 KB Output is correct
10 Correct 88 ms 6912 KB Output is correct
11 Correct 89 ms 6912 KB Output is correct
12 Correct 91 ms 7028 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 6212 KB Output is correct
2 Correct 204 ms 6384 KB Output is correct
3 Correct 364 ms 5764 KB Output is correct
4 Correct 246 ms 5028 KB Output is correct
5 Correct 360 ms 10692 KB Output is correct
6 Correct 438 ms 10564 KB Output is correct
7 Correct 348 ms 10628 KB Output is correct
8 Correct 582 ms 10564 KB Output is correct
9 Correct 478 ms 10576 KB Output is correct
10 Correct 576 ms 10836 KB Output is correct
11 Correct 381 ms 10544 KB Output is correct
12 Correct 843 ms 10564 KB Output is correct