oj.uz

Submission #907651

# Submission time Handle Problem Language Result Execution time Memory
907651 2024-01-16T01:27:38 Z andro Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 585 ms 12120 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

struct segtree{
    int t[4*N];
    int query(int v,int tl,int tr,int l,int r){
        if(tl>r||tr<l)return 0;
        if(tl>=l&&tr<=r)return t[v];
        int tm=(tl+tr)/2;
        return query(v*2,tl,tm,l,r)+query(v*2+1,tm+1,tr,l,r);
    }
    void update(int v,int tl,int tr,int index,int value){
        if(tl==tr)t[v]=value;
        else {
            int tm=(tl+tr)/2;
            if(index<=tm)update(v*2,tl,tm,index,value);
            else update(v*2+1,tm+1,tr,index,value);
            t[v]=t[v*2]+t[v*2+1];
        }
    }
    int query(int l, int r) {
        return query(1, 1, N, l, r);
    }
    void update(int i, int value) {
        update(1, 1, N, i, value);
    }
}seg;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q, k;
    cin >> n >> q >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        seg.update(i, a[i]);
    }
    set<int> s;
    for(int i = 1; i <= n; i++) {
        s.insert(i);
    }
    vector<int> P(n + 1);
    const int limit = 33;
    while(q--) {
        int o;
        cin >> o;
        if(o == 1) {
            int l, r;
            cin >> l >> r;
            seg.update(l, r);
        }
        else if(o == 2) {
            int l, r;
            cin >> l >> r;
            auto it = s.lower_bound(l);
            vector<int> V;
            while(*it <= r && it != s.end()) {
                int x = seg.query(*it, *it);
                seg.update(*it, x / k);
                P[*it] += 1;
                if(P[*it] > limit) {
                    V.push_back(*it);
                }
                it++;
            }
            for(auto it : V) {
                s.erase(it);
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << seg.query(l, r) << "\n";
        }
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 6032 KB Output is correct
2 Correct 203 ms 4944 KB Output is correct
3 Correct 445 ms 7748 KB Output is correct
4 Correct 551 ms 9044 KB Output is correct
5 Correct 569 ms 11860 KB Output is correct
6 Correct 574 ms 11904 KB Output is correct
7 Correct 585 ms 12080 KB Output is correct
8 Correct 568 ms 12120 KB Output is correct
9 Correct 569 ms 11720 KB Output is correct
10 Correct 570 ms 11960 KB Output is correct
11 Correct 581 ms 11956 KB Output is correct
12 Correct 564 ms 11704 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 5972 KB Output isn't correct
2 Halted 0 ms 0 KB -