oj.uz

Submission #723960

# Submission time Handle Problem Language Result Execution time Memory
723960 2023-04-14T14:22:42 Z kkts Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 234 ms 7076 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);
    s.insert(n + 5);
    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] / k != c[x]) 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 Incorrect 1 ms 340 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 38 ms 3788 KB Output is correct
2 Correct 41 ms 2764 KB Output is correct
3 Correct 41 ms 5388 KB Output is correct
4 Correct 56 ms 6860 KB Output is correct
5 Correct 66 ms 6940 KB Output is correct
6 Correct 56 ms 6936 KB Output is correct
7 Correct 62 ms 6924 KB Output is correct
8 Correct 66 ms 6956 KB Output is correct
9 Correct 65 ms 7048 KB Output is correct
10 Correct 75 ms 7000 KB Output is correct
11 Correct 60 ms 6988 KB Output is correct
12 Correct 56 ms 7076 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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