oj.uz

Submission #224601

# Submission time Handle Problem Language Result Execution time Memory
224601 2020-04-18T13:36:47 Z PeppaPig Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 731 ms 66680 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 1 << 17;

int n, q, k;

struct node {
    vector<long> vec;
    node() {}
    node(int x) {
        if(k == 1) vec.emplace_back(x);
        else while(x) {
            vec.emplace_back(x);
            x /= k;
        }
    }
    friend node operator+(const node &a, const node &b) {
        node ret;
        ret.vec = a.vec;
        for(int i = 0; i < b.vec.size(); i++) {
            if(ret.vec.size() <= i) ret.vec.emplace_back(b.vec[i]);
            else ret.vec[i] += b.vec[i];
        }
        while(!ret.vec.empty() && !ret.vec.back()) 
            ret.vec.pop_back();
        return ret;
    }

    void shift(int x) {
        reverse(vec.begin(), vec.end());
        while(!vec.empty() && x--) 
            vec.pop_back();
        reverse(vec.begin(), vec.end());
    }

    long get() { return vec.empty() ? 0 : vec.front(); }
} t[N << 1];

int lz[N << 1], A[N];

void build(int p = 1, int l = 1, int r = n) {
    if(l == r) return void(t[p] = node(A[l]));
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

void push(int p, int l, int r) {
    if(lz[p]) {
        t[p].shift(lz[p]);
        if(l != r) {
            lz[p << 1] += lz[p];
            lz[p << 1 | 1] += lz[p];
        }
        lz[p] = 0;
    }
}

void update(int x, int _k, int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(x < l || r < x) return;
    if(l == r) return void(t[p] = node(_k));
    int mid = (l + r) >> 1;
    update(x, _k, p << 1, l, mid), update(x, _k, p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

void spray(int x, int y, int p = 1, int l = 1, int r = n) {
    if(k == 1) return;
    push(p, l, r);
    if(x > r || l > y) return;
    if(x <= l && r <= y) {
        ++lz[p], push(p, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    spray(x, y, p << 1, l, mid), spray(x, y, p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

long query(int x, int y, int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(x > r || l > y) return 0;
    if(x <= l && r <= y) return t[p].get();
    int mid = (l + r) >> 1;
    return query(x, y, p << 1, l, mid) + query(x, y, p << 1 | 1, mid + 1, r);
}

void print(int p = 1, int l = 1, int r = n) {
    push(p, l, r);
    if(l == r) return void(printf("%d ", t[p].get()));
    int mid = (l + r) >> 1;
    print(p << 1, l, mid), print(p << 1 | 1, mid + 1, r);
} 

int main() {
    scanf("%d %d %d", &n, &q, &k);
    for(int i = 1; i <= n; i++) scanf("%d", A + i);

    build();
    for(int i = 1, T, a, b; i <= q; i++) {
        scanf("%d %d %d", &T, &a, &b);
        if(T == 1) update(a, b);
        else if(T == 2) spray(a, b);
        else printf("%lld\n", query(a, b));
    }

    return 0;
}

Compilation message

sterilizing.cpp: In function 'node operator+(const node&, const node&)':
sterilizing.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < b.vec.size(); i++) {
                        ~~^~~~~~~~~~~~~~
sterilizing.cpp:25:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ret.vec.size() <= i) ret.vec.emplace_back(b.vec[i]);
                ~~~~~~~~~~~~~~~^~~~
sterilizing.cpp: In function 'void print(int, int, int)':
sterilizing.cpp:95:52: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     if(l == r) return void(printf("%d ", t[p].get()));
                                          ~~~~~~~~~~^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &q, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:102:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", A + i);
                                 ~~~~~^~~~~~~~~~~~~
sterilizing.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &T, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6528 KB Output is correct
2 Correct 9 ms 6528 KB Output is correct
3 Correct 10 ms 6912 KB Output is correct
4 Correct 20 ms 7296 KB Output is correct
5 Correct 19 ms 7424 KB Output is correct
6 Correct 17 ms 7296 KB Output is correct
7 Correct 21 ms 7424 KB Output is correct
8 Correct 18 ms 7552 KB Output is correct
9 Correct 20 ms 7936 KB Output is correct
10 Correct 19 ms 7424 KB Output is correct
11 Correct 20 ms 7424 KB Output is correct
12 Correct 18 ms 7424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 10236 KB Output is correct
2 Correct 134 ms 10804 KB Output is correct
3 Correct 139 ms 13596 KB Output is correct
4 Correct 179 ms 15584 KB Output is correct
5 Correct 212 ms 16160 KB Output is correct
6 Correct 207 ms 16228 KB Output is correct
7 Correct 203 ms 16084 KB Output is correct
8 Correct 203 ms 16132 KB Output is correct
9 Correct 182 ms 15936 KB Output is correct
10 Correct 189 ms 15964 KB Output is correct
11 Correct 180 ms 15992 KB Output is correct
12 Correct 180 ms 15968 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6908 KB Output is correct
2 Correct 55 ms 9256 KB Output is correct
3 Correct 56 ms 9156 KB Output is correct
4 Correct 147 ms 7936 KB Output is correct
5 Correct 209 ms 12284 KB Output is correct
6 Correct 214 ms 12280 KB Output is correct
7 Correct 182 ms 13304 KB Output is correct
8 Correct 199 ms 12280 KB Output is correct
9 Correct 175 ms 12280 KB Output is correct
10 Correct 162 ms 12280 KB Output is correct
11 Correct 174 ms 12284 KB Output is correct
12 Correct 172 ms 12280 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 19576 KB Output is correct
2 Correct 326 ms 20448 KB Output is correct
3 Correct 355 ms 33656 KB Output is correct
4 Correct 379 ms 17912 KB Output is correct
5 Correct 470 ms 34820 KB Output is correct
6 Correct 518 ms 36440 KB Output is correct
7 Correct 473 ms 32220 KB Output is correct
8 Correct 731 ms 54396 KB Output is correct
9 Correct 490 ms 40336 KB Output is correct
10 Correct 565 ms 57080 KB Output is correct
11 Correct 475 ms 36728 KB Output is correct
12 Correct 675 ms 66680 KB Output is correct