oj.uz

Submission #602406

# Submission time Handle Problem Language Result Execution time Memory
602406 2022-07-23T04:13:13 Z Hanksburger Sterilizing Spray (JOI15_sterilizing) C++17
5 / 100
 5000 ms 110344 KB 
#include <bits/stdc++.h>
using namespace std;
long long seg[400005], a[100005];
set<int> s[400005], t;
int n, q, k;
void build(int i, int l, int r)
{
    if (l==r)
    {
        seg[i]=a[l];
        if (a[l])
            s[i].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];
    s[i].insert(s[i*2].begin(), s[i*2].end());
    s[i].insert(s[i*2+1].begin(), s[i*2+1].end());
}
void update(int i, int l, int r, int y, int z)
{
    if (l==r)
    {
        seg[i]=a[y]=z;
        s[i].erase(y);
        if (z)
            s[i].insert(y);
        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];
    s[i].erase(y);
    if (z)
        s[i].insert(y);
}
void spray(int i, int l, int r, int y, int z)
{
//    cout << "spray " << l << ' ' << r << '\n';
    if (y<=l && r<=z)
    {
        t.insert(s[i].begin(), s[i].end());
        return;
    }
    int mid=(l+r)/2;
    if (l<=z && y<=mid)
        spray(i*2, l, mid, y, z);
    if (mid+1<=z && y<=r)
        spray(i*2+1, mid+1, r, y, z);
}
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);
        else if (x==2)
        {
            t.clear();
            spray(1, 1, n, y, z);
            for (int i:t)
//            {
//                cout << "i=" << i << '\n';
                update(1, 1, n, i, a[i]/k);
//            }
        }
        else
            cout << query(1, 1, n, y, z) << '\n';
//        for (int i=1; i<=n; i++)
//            cout << a[i] << ' ';
//        cout << '\n';
//        for (int i:s[1])
//            cout << i << '\n';
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 19156 KB Output is correct
2 Correct 104 ms 19552 KB Output is correct
3 Correct 35 ms 20152 KB Output is correct
4 Correct 105 ms 19988 KB Output is correct
5 Correct 105 ms 21136 KB Output is correct
6 Correct 68 ms 21136 KB Output is correct
7 Correct 87 ms 21148 KB Output is correct
8 Correct 87 ms 21076 KB Output is correct
9 Correct 126 ms 21148 KB Output is correct
10 Correct 85 ms 21064 KB Output is correct
11 Correct 93 ms 21264 KB Output is correct
12 Correct 107 ms 21112 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 60656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 21368 KB Output is correct
2 Correct 80 ms 38068 KB Output is correct
3 Correct 88 ms 38792 KB Output is correct
4 Correct 118 ms 30004 KB Output is correct
5 Correct 253 ms 65456 KB Output is correct
6 Correct 234 ms 65216 KB Output is correct
7 Execution timed out 5066 ms 65708 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2158 ms 63680 KB Output is correct
2 Correct 2001 ms 64736 KB Output is correct
3 Correct 4890 ms 58472 KB Output is correct
4 Correct 2137 ms 46896 KB Output is correct
5 Correct 4135 ms 110344 KB Output is correct
6 Execution timed out 5082 ms 109632 KB Time limit exceeded
7 Halted 0 ms 0 KB -