oj.uz

Submission #602439

# Submission time Handle Problem Language Result Execution time Memory
602439 2022-07-23T06:07:04 Z Hanksburger Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 10516 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)
        {
            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 3 ms 340 KB Output is correct
2 Correct 6 ms 416 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 9 ms 500 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 10 ms 596 KB Output is correct
8 Correct 9 ms 596 KB Output is correct
9 Correct 13 ms 596 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 9 ms 640 KB Output is correct
12 Correct 8 ms 596 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Correct 17 ms 2764 KB Output is correct
3 Correct 21 ms 2704 KB Output is correct
4 Correct 42 ms 1632 KB Output is correct
5 Correct 66 ms 5512 KB Output is correct
6 Correct 67 ms 5536 KB Output is correct
7 Execution timed out 5094 ms 5504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 4352 KB Output is correct
2 Correct 177 ms 5536 KB Output is correct
3 Correct 255 ms 5068 KB Output is correct
4 Correct 164 ms 3944 KB Output is correct
5 Correct 266 ms 9228 KB Output is correct
6 Correct 302 ms 9844 KB Output is correct
7 Correct 258 ms 10512 KB Output is correct
8 Correct 399 ms 10516 KB Output is correct
9 Correct 366 ms 10516 KB Output is correct
10 Correct 389 ms 10460 KB Output is correct
11 Correct 282 ms 10444 KB Output is correct
12 Correct 580 ms 10384 KB Output is correct