oj.uz

Submission #602441

# Submission time Handle Problem Language Result Execution time Memory
602441 2022-07-23T06:08:52 Z Hanksburger Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 558 ms 10780 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);
//            cout << "insert " << l << '\n';
        }
        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;
//        cout << "delete " << y << '\n';
//        s.erase(y);
//        if (z)
//        {
//            s.insert(y);
////            cout << "insert " << y << '\n';
//        }
        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--)
    {
//        cout << "q=" << q << '\n';
        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;
    //                cout << "i = " << i << '\n';
                    update(1, 1, n, i, a[i]/k);
                    itr++;
                    if (!a[i])
                        s.erase(i);
    //                cout << "updated a[" << i << "] to " << a[i] << '\n';
    //                if (a[i])
    //                {
    ////                    cout << "s: ";
    ////                    for (int iii:s)
    ////                        cout << iii << ' ';
    ////                    cout << '\n';
    ////                    cout << "itr was pointing at " << (*itr) << '\n';
    //                    if ((*itr)==(*s.rbegin()))
    //                        break;
    //                    itr++;
    //                }
    //                else
    //                {
    //                    itr=s.lower_bound(i);
    ////                    if(i==4)
    ////                        cout << "i am 4\n";
    //                }
    //                cout << "s: ";
    //                for (int i:s)
    //                    cout << i << ' ';
    //                cout << '\n';
                }
            }
        }
        else
            cout << query(1, 1, n, y, z) << '\n';
//        for (int i=1; i<=n; i++)
//            cout << a[i] << ' ';
//        cout << '\n';
//        cout << "s: ";
//        for (int i:s)
//            cout << i << ' ';
//        cout << '\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 3 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 8 ms 572 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 468 KB Output is correct
9 Correct 9 ms 568 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 7 ms 568 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 63 ms 5584 KB Output is correct
2 Correct 51 ms 5104 KB Output is correct
3 Correct 57 ms 8544 KB Output is correct
4 Correct 74 ms 10276 KB Output is correct
5 Correct 89 ms 10744 KB Output is correct
6 Correct 86 ms 10700 KB Output is correct
7 Correct 89 ms 10780 KB Output is correct
8 Correct 89 ms 10684 KB Output is correct
9 Correct 86 ms 10580 KB Output is correct
10 Correct 85 ms 10624 KB Output is correct
11 Correct 91 ms 10620 KB Output is correct
12 Correct 82 ms 10640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 676 KB Output is correct
2 Correct 17 ms 2760 KB Output is correct
3 Correct 20 ms 2768 KB Output is correct
4 Correct 42 ms 1660 KB Output is correct
5 Correct 67 ms 5508 KB Output is correct
6 Correct 70 ms 5640 KB Output is correct
7 Correct 66 ms 6604 KB Output is correct
8 Correct 65 ms 6900 KB Output is correct
9 Correct 59 ms 6792 KB Output is correct
10 Correct 62 ms 6796 KB Output is correct
11 Correct 67 ms 6776 KB Output is correct
12 Correct 63 ms 6884 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4348 KB Output is correct
2 Correct 144 ms 4352 KB Output is correct
3 Correct 248 ms 3944 KB Output is correct
4 Correct 168 ms 2804 KB Output is correct
5 Correct 258 ms 8064 KB Output is correct
6 Correct 299 ms 8144 KB Output is correct
7 Correct 232 ms 8076 KB Output is correct
8 Correct 398 ms 8104 KB Output is correct
9 Correct 324 ms 8116 KB Output is correct
10 Correct 378 ms 8156 KB Output is correct
11 Correct 262 ms 8140 KB Output is correct
12 Correct 558 ms 8224 KB Output is correct