oj.uz

Submission #723957

# Submission time Handle Problem Language Result Execution time Memory
723957 2023-04-14T14:15:47 Z kkts Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 5000 ms 9508 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t[N], c[N], n;
void upd(int id, int v) {
    for(id; id <= n; id += id & (-id)) t[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += t[id];
    return ans;
}
void update(int x, int v) {
    if(c[x] == v) return;
    upd(x, -c[x]);
    c[x] = v;
    upd(x, c[x]);
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int  q, k;
    cin >> n >> q >> k;
    set<int> s;
    for(int i = 1; i <= n; i++) cin >> c[i], upd(i, c[i]), s.insert(i);
    for(int i = 1; i <= q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
//        for(int j = 1; j <= n; j++) cout << c[j] << " ";
        if(t == 1) {
            update(l, r);
            continue;
        }
        if(t == 2) {
            int L = l - 1;
            while(k > 1 && *s.upper_bound(L) <= r) {
                int x = *s.upper_bound(L);
                s.erase(x);
                update(x, c[x] / k);
                if(c[x] > 0) s.insert(x);
                L = x;
            }
        } else cout << get(r) - get(l - 1) << "\n";
    }
 }

Compilation message

sterilizing.cpp: In function 'void upd(long long int, long long int)':
sterilizing.cpp:10:9: warning: statement has no effect [-Wunused-value]
   10 |     for(id; id <= n; id += id & (-id)) t[id] += v;
      |         ^~
sterilizing.cpp: In function 'long long int get(long long int)':
sterilizing.cpp:14:9: warning: statement has no effect [-Wunused-value]
   14 |     for(id; id >= 1; id -= id & (-id)) ans += t[id];
      |         ^~
sterilizing.cpp: At global scope:
sterilizing.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main(){
      | ^~~~

Subtask #1
0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5632 KB Output is correct
2 Correct 52 ms 4428 KB Output is correct
3 Correct 45 ms 7052 KB Output is correct
4 Correct 57 ms 8948 KB Output is correct
5 Correct 66 ms 9416 KB Output is correct
6 Correct 76 ms 9420 KB Output is correct
7 Correct 66 ms 9420 KB Output is correct
8 Correct 63 ms 9508 KB Output is correct
9 Correct 66 ms 9288 KB Output is correct
10 Correct 63 ms 9292 KB Output is correct
11 Correct 66 ms 9344 KB Output is correct
12 Correct 75 ms 9328 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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