oj.uz

Submission #907662

# Submission time Handle Problem Language Result Execution time Memory
907662 2024-01-16T01:32:06 Z andro Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 1822 ms 10224 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 = 100;
    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 876 ms 5988 KB Output is correct
2 Correct 592 ms 5096 KB Output is correct
3 Correct 1384 ms 7608 KB Output is correct
4 Correct 1814 ms 9132 KB Output is correct
5 Correct 1780 ms 9412 KB Output is correct
6 Correct 1714 ms 9192 KB Output is correct
7 Correct 1693 ms 9460 KB Output is correct
8 Correct 1698 ms 9456 KB Output is correct
9 Correct 1695 ms 10084 KB Output is correct
10 Correct 1715 ms 10184 KB Output is correct
11 Correct 1688 ms 10224 KB Output is correct
12 Correct 1822 ms 10088 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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