oj.uz

Submission #224593

# Submission time Handle Problem Language Result Execution time Memory
224593 2020-04-18T13:24:55 Z PeppaPig Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 259 ms 14712 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 1 << 17;

int n, q, k;

struct node {
    vector<int> 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());
    }

    int 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 (long)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 '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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6904 KB Output is correct
2 Correct 40 ms 9088 KB Output is correct
3 Correct 59 ms 9192 KB Output is correct
4 Correct 149 ms 7936 KB Output is correct
5 Correct 225 ms 12280 KB Output is correct
6 Correct 196 ms 12280 KB Output is correct
7 Correct 172 ms 14712 KB Output is correct
8 Correct 225 ms 13688 KB Output is correct
9 Correct 185 ms 13560 KB Output is correct
10 Correct 168 ms 13560 KB Output is correct
11 Correct 176 ms 13688 KB Output is correct
12 Correct 179 ms 13560 KB Output is correct

Subtask #4
0 / 75.0

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