oj.uz

답안 #380543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380543 2021-03-22T08:43:34 Z Aryan_Raina Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 1373 ms 198136 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array

const int INF = 1e17;
const int MOD = 1e9;

struct SegTree {
    vector<deque<int>> values;
    vector<int> operations;
    int size, k;
    void init(int n, int _k) {
        size = 1; k = _k;
        while (size < n) size <<= 1;
        operations.resize(2*size);
        values.resize(2*size);
    }
    void propogate(int x, int lx, int rx) {
        if (rx - lx != 1) {
            operations[2*x+1] += operations[x];
            operations[2*x+2] += operations[x];
        } 
        for ( ; operations[x] && values[x].size() > 1; operations[x]--) values[x].pop_front();
        operations[x] = 0;
    }
    void update(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        int m = (lx + rx) >> 1;
        while (values[x].size() > 0) values[x].pop_front();
        propogate(2*x+1, lx, m);
        propogate(2*x+2, m, rx);
        int i, j;
        for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {  
            values[x].push_back(values[2*x+1][i] + values[2*x+2][j]);
        }
        for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
            for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
    }
    void set(int i, int v, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (rx - lx == 1) {
            while (values[x].size() > 0) values[x].pop_front();
            while (v && k > 1) {
                values[x].push_back(v); v /= k;
            }
            values[x].push_back(v);
            return;
        }
        int m = (lx + rx) >> 1;
        if (i < m) set(i, v, 2*x+1, lx, m);
        else set(i, v, 2*x+2, m, rx);
        update(x, lx, rx);
    }
    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }
    void modify(int l, int r, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (lx >= r || l >= rx) return;
        if (l <= lx && rx <= r) return void(operations[x]++);
        int m = (lx + rx) >> 1;
        modify(l, r, 2*x+1, lx, m);
        modify(l, r, 2*x+2, m, rx);
        update(x, lx, rx);
    }
    void modify(int l, int r) {
        modify(l, r, 0, 0, size);
    }
    int calc(int l, int r, int x, int lx, int rx) {
        propogate(x, lx, rx);
        if (lx >= r || l >= rx) return 0;
        if (l <= lx && rx <= r) {
            return values[x].front();
        }
        int m = (lx + rx) >> 1;
        int s1 = calc(l, r, 2*x+1, lx, m);
        int s2 = calc(l, r, 2*x+2, m, rx);
        return s1 + s2;
    }
    int calc(int l, int r) {
        return calc(l, r, 0, 0, size);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k; cin>>n>>m>>k;
    SegTree st; st.init(n, k);
    for (int i = 0; i < n; i++) {
        int x; cin>>x;
        st.set(i, x);
    }
    while (m--) {
        int t, a, b; cin>>t>>a>>b;
        if (t == 1) {
            st.set(a-1, b);
        } else if (t == 2 && k > 1) {
            st.modify(a-1, b);
        } else if (t == 3) {
            cout<<st.calc(a-1, b)<<"\n";
        }
    }
}

Compilation message

sterilizing.cpp: In member function 'void SegTree::update(long long int, long long int, long long int)':
sterilizing.cpp:36:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:36:58: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
      |                                                        ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:39:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
      |                ~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:40:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 492 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 6 ms 3180 KB Output is correct
4 Correct 19 ms 3436 KB Output is correct
5 Correct 20 ms 6508 KB Output is correct
6 Correct 16 ms 6124 KB Output is correct
7 Correct 19 ms 6124 KB Output is correct
8 Correct 19 ms 6124 KB Output is correct
9 Correct 24 ms 6508 KB Output is correct
10 Correct 18 ms 6124 KB Output is correct
11 Correct 19 ms 6124 KB Output is correct
12 Correct 21 ms 6124 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 92140 KB Output is correct
2 Correct 202 ms 91884 KB Output is correct
3 Correct 295 ms 181740 KB Output is correct
4 Correct 341 ms 182124 KB Output is correct
5 Correct 387 ms 182380 KB Output is correct
6 Correct 385 ms 182380 KB Output is correct
7 Correct 378 ms 182380 KB Output is correct
8 Correct 390 ms 182764 KB Output is correct
9 Correct 350 ms 182252 KB Output is correct
10 Correct 350 ms 183276 KB Output is correct
11 Correct 352 ms 182636 KB Output is correct
12 Correct 354 ms 183276 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 11628 KB Output is correct
2 Correct 150 ms 90380 KB Output is correct
3 Correct 174 ms 90348 KB Output is correct
4 Correct 271 ms 45420 KB Output is correct
5 Correct 566 ms 180716 KB Output is correct
6 Correct 567 ms 180588 KB Output is correct
7 Correct 373 ms 182020 KB Output is correct
8 Correct 572 ms 182124 KB Output is correct
9 Correct 449 ms 181868 KB Output is correct
10 Correct 447 ms 181868 KB Output is correct
11 Correct 448 ms 181868 KB Output is correct
12 Correct 453 ms 181868 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 90568 KB Output is correct
2 Correct 536 ms 91452 KB Output is correct
3 Correct 703 ms 92908 KB Output is correct
4 Correct 617 ms 51308 KB Output is correct
5 Correct 884 ms 180588 KB Output is correct
6 Correct 1042 ms 181740 KB Output is correct
7 Correct 884 ms 182092 KB Output is correct
8 Correct 1218 ms 196204 KB Output is correct
9 Correct 897 ms 198136 KB Output is correct
10 Correct 1049 ms 196204 KB Output is correct
11 Correct 778 ms 183788 KB Output is correct
12 Correct 1373 ms 195112 KB Output is correct