oj.uz

Submission #907656

# Submission time Handle Problem Language Result Execution time Memory
907656 2024-01-16T01:29:43 Z andro Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 679 ms 10184 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int n;

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 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 348 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 317 ms 5980 KB Output is correct
2 Correct 216 ms 5028 KB Output is correct
3 Correct 499 ms 7764 KB Output is correct
4 Correct 636 ms 9160 KB Output is correct
5 Correct 652 ms 9308 KB Output is correct
6 Correct 637 ms 9388 KB Output is correct
7 Correct 649 ms 9452 KB Output is correct
8 Correct 679 ms 9220 KB Output is correct
9 Correct 646 ms 10184 KB Output is correct
10 Correct 647 ms 10088 KB Output is correct
11 Correct 665 ms 10080 KB Output is correct
12 Correct 625 ms 10084 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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