oj.uz

Submission #907657

# Submission time Handle Problem Language Result Execution time Memory
907657 2024-01-16T01:30:24 Z andro Sterilizing Spray (JOI15_sterilizing) C++14
5 / 100
 5000 ms 5964 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 = 1000;
    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 36 ms 584 KB Output is correct
5 Correct 92 ms 600 KB Output is correct
6 Correct 97 ms 600 KB Output is correct
7 Correct 92 ms 712 KB Output is correct
8 Correct 86 ms 604 KB Output is correct
9 Correct 97 ms 604 KB Output is correct
10 Correct 95 ms 716 KB Output is correct
11 Correct 90 ms 716 KB Output is correct
12 Correct 98 ms 604 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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