oj.uz

Submission #602443

# Submission time Handle Problem Language Result Execution time Memory
602443 2022-07-23T06:10:18 Z Hanksburger Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 588 ms 8336 KB 
#include <bits/stdc++.h>
using namespace std;
long long seg[400005], a[100005];
int n, q, k;
set<int> s;
void build(int i, int l, int r)
{
    if (l==r)
    {
        seg[i]=a[l];
        if (a[l])
            s.insert(l);
        return;
    }
    int mid=(l+r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    seg[i]=seg[i*2]+seg[i*2+1];
}
void update(int i, int l, int r, int y, int z)
{
    if (l==r)
    {
        seg[i]=a[y]=z;
        return;
    }
    int mid=(l+r)/2;
    if (y<=mid)
        update(i*2, l, mid, y, z);
    else
        update(i*2+1, mid+1, r, y, z);
    seg[i]=seg[i*2]+seg[i*2+1];
}
long long query(int i, int l, int r, int y, int z)
{
    if (y<=l && r<=z)
        return seg[i];
    int mid=(l+r)/2;
    long long res=0;
    if (l<=z && y<=mid)
        res+=query(i*2, l, mid, y, z);
    if (mid+1<=z && y<=r)
        res+=query(i*2+1, mid+1, r, y, z);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q >> k;
    for (int i=1; i<=n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if (x==1)
        {
            update(1, 1, n, y, z);
            s.erase(y);
            if (z)
                s.insert(y);
        }
        else if (x==2)
        {
            if (k>=2)
            {
                auto itr=s.lower_bound(y);
                while (itr!=s.end() && (*itr)<=z)
                {
                    int i=*itr;
                    update(1, 1, n, i, a[i]/k);
                    itr++;
                    if (!a[i])
                        s.erase(i);
                }
            }
        }
        else
            cout << query(1, 1, n, y, z) << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 7 ms 564 KB Output is correct
9 Correct 9 ms 468 KB Output is correct
10 Correct 7 ms 568 KB Output is correct
11 Correct 10 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4420 KB Output is correct
2 Correct 49 ms 3580 KB Output is correct
3 Correct 55 ms 6860 KB Output is correct
4 Correct 77 ms 8140 KB Output is correct
5 Correct 85 ms 8220 KB Output is correct
6 Correct 84 ms 8228 KB Output is correct
7 Correct 89 ms 8280 KB Output is correct
8 Correct 85 ms 8268 KB Output is correct
9 Correct 87 ms 8336 KB Output is correct
10 Correct 82 ms 8268 KB Output is correct
11 Correct 100 ms 8312 KB Output is correct
12 Correct 106 ms 8324 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 596 KB Output is correct
2 Correct 17 ms 2760 KB Output is correct
3 Correct 22 ms 2876 KB Output is correct
4 Correct 46 ms 1668 KB Output is correct
5 Correct 64 ms 5496 KB Output is correct
6 Correct 64 ms 5480 KB Output is correct
7 Correct 64 ms 5644 KB Output is correct
8 Correct 66 ms 5536 KB Output is correct
9 Correct 63 ms 5504 KB Output is correct
10 Correct 61 ms 5624 KB Output is correct
11 Correct 59 ms 5504 KB Output is correct
12 Correct 59 ms 5532 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 4320 KB Output is correct
2 Correct 160 ms 4336 KB Output is correct
3 Correct 291 ms 3932 KB Output is correct
4 Correct 169 ms 2852 KB Output is correct
5 Correct 242 ms 8012 KB Output is correct
6 Correct 295 ms 8156 KB Output is correct
7 Correct 235 ms 8024 KB Output is correct
8 Correct 399 ms 8080 KB Output is correct
9 Correct 323 ms 8160 KB Output is correct
10 Correct 402 ms 8252 KB Output is correct
11 Correct 282 ms 8092 KB Output is correct
12 Correct 588 ms 8100 KB Output is correct