oj.uz

Submission #723962

# Submission time Handle Problem Language Result Execution time Memory
723962 2023-04-14T14:24:25 Z kkts Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1648 ms 9284 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;
        if(t == 1) {
            update(l, r);
            s.insert(l);
            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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 16 ms 468 KB Output is correct
5 Correct 15 ms 584 KB Output is correct
6 Correct 12 ms 592 KB Output is correct
7 Correct 12 ms 596 KB Output is correct
8 Correct 15 ms 588 KB Output is correct
9 Correct 21 ms 612 KB Output is correct
10 Correct 12 ms 596 KB Output is correct
11 Correct 16 ms 600 KB Output is correct
12 Correct 19 ms 580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3716 KB Output is correct
2 Correct 55 ms 2800 KB Output is correct
3 Correct 51 ms 5408 KB Output is correct
4 Correct 58 ms 6908 KB Output is correct
5 Correct 75 ms 6988 KB Output is correct
6 Correct 73 ms 6944 KB Output is correct
7 Correct 88 ms 6960 KB Output is correct
8 Correct 96 ms 6960 KB Output is correct
9 Correct 72 ms 6952 KB Output is correct
10 Correct 71 ms 7040 KB Output is correct
11 Correct 84 ms 7060 KB Output is correct
12 Correct 73 ms 6988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 724 KB Output is correct
2 Correct 24 ms 3284 KB Output is correct
3 Correct 27 ms 3508 KB Output is correct
4 Correct 41 ms 3012 KB Output is correct
5 Correct 71 ms 7968 KB Output is correct
6 Correct 74 ms 7964 KB Output is correct
7 Correct 88 ms 8172 KB Output is correct
8 Correct 93 ms 8000 KB Output is correct
9 Correct 76 ms 7840 KB Output is correct
10 Correct 69 ms 7848 KB Output is correct
11 Correct 66 ms 7852 KB Output is correct
12 Correct 65 ms 7884 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 3652 KB Output is correct
2 Correct 273 ms 5472 KB Output is correct
3 Correct 606 ms 4392 KB Output is correct
4 Correct 350 ms 4300 KB Output is correct
5 Correct 536 ms 9284 KB Output is correct
6 Correct 700 ms 9252 KB Output is correct
7 Correct 573 ms 9244 KB Output is correct
8 Correct 995 ms 9252 KB Output is correct
9 Correct 853 ms 9124 KB Output is correct
10 Correct 1040 ms 9204 KB Output is correct
11 Correct 605 ms 9204 KB Output is correct
12 Correct 1648 ms 9220 KB Output is correct