oj.uz

Submission #224603

# Submission time Handle Problem Language Result Execution time Memory
224603 2020-04-18T13:37:34 Z PeppaPig Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 723 ms 64120 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);
}

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 'int main()':
sterilizing.cpp:94: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:95: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:99: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 13 ms 6528 KB Output is correct
2 Correct 10 ms 6528 KB Output is correct
3 Correct 10 ms 6912 KB Output is correct
4 Correct 18 ms 7296 KB Output is correct
5 Correct 18 ms 7424 KB Output is correct
6 Correct 17 ms 7296 KB Output is correct
7 Correct 17 ms 7424 KB Output is correct
8 Correct 17 ms 7424 KB Output is correct
9 Correct 25 ms 7808 KB Output is correct
10 Correct 18 ms 7424 KB Output is correct
11 Correct 23 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 137 ms 10312 KB Output is correct
2 Correct 123 ms 9080 KB Output is correct
3 Correct 117 ms 11896 KB Output is correct
4 Correct 165 ms 13408 KB Output is correct
5 Correct 195 ms 13560 KB Output is correct
6 Correct 184 ms 13560 KB Output is correct
7 Correct 183 ms 13560 KB Output is correct
8 Correct 203 ms 13688 KB Output is correct
9 Correct 159 ms 13688 KB Output is correct
10 Correct 165 ms 13688 KB Output is correct
11 Correct 192 ms 13640 KB Output is correct
12 Correct 161 ms 13688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6904 KB Output is correct
2 Correct 41 ms 9088 KB Output is correct
3 Correct 56 ms 9088 KB Output is correct
4 Correct 145 ms 7984 KB Output is correct
5 Correct 217 ms 12280 KB Output is correct
6 Correct 191 ms 12280 KB Output is correct
7 Correct 177 ms 13304 KB Output is correct
8 Correct 217 ms 12284 KB Output is correct
9 Correct 166 ms 12280 KB Output is correct
10 Correct 173 ms 12260 KB Output is correct
11 Correct 164 ms 12280 KB Output is correct
12 Correct 175 ms 12280 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 19576 KB Output is correct
2 Correct 301 ms 18680 KB Output is correct
3 Correct 381 ms 32648 KB Output is correct
4 Correct 363 ms 16248 KB Output is correct
5 Correct 494 ms 32300 KB Output is correct
6 Correct 477 ms 34040 KB Output is correct
7 Correct 489 ms 29720 KB Output is correct
8 Correct 723 ms 51932 KB Output is correct
9 Correct 473 ms 37880 KB Output is correct
10 Correct 577 ms 54776 KB Output is correct
11 Correct 455 ms 34424 KB Output is correct
12 Correct 711 ms 64120 KB Output is correct