oj.uz

Submission #907659

# Submission time Handle Problem Language Result Execution time Memory
907659 2024-01-16T01:30:57 Z andro Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 899 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 = 50;
    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 1 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 444 ms 5968 KB Output is correct
2 Correct 300 ms 5012 KB Output is correct
3 Correct 687 ms 7764 KB Output is correct
4 Correct 892 ms 9112 KB Output is correct
5 Correct 892 ms 9456 KB Output is correct
6 Correct 892 ms 9344 KB Output is correct
7 Correct 884 ms 9456 KB Output is correct
8 Correct 883 ms 9296 KB Output is correct
9 Correct 892 ms 9932 KB Output is correct
10 Correct 897 ms 10184 KB Output is correct
11 Correct 888 ms 10184 KB Output is correct
12 Correct 899 ms 10080 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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