oj.uz

Submission #153112

# Submission time Handle Problem Language Result Execution time Memory
153112 2019-09-12T12:53:48 Z karma Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 242 ms 9184 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll      long long
#define pb      emplace_back

using namespace std;

const int N = int(1e5) + 2;

int n, q, k, a[N], irene, cmd, x, y;
ll t[N];
set<int> s;
vector<int> rmv;

void Update(int x, int val) {
     for(; x <= n; x += (x & -x)) t[x] += val;
}

ll Query(int x) {
    ll res = 0;
    for(; x > 0; x -= (x & -x)) res += t[x];
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> q >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i]; Update(i, a[i]);
        if(a[i]) s.insert(i);
    }
    rmv.clear();
    while(q --) {
        cin >> cmd >> x >> y;
        if(cmd == 1) {
            if(y && !a[x]) s.insert(x);
            Update(x, y - a[x]); a[x] = y;
        } else if(cmd == 2) {
           if(k == 1) continue;
           auto ptr = s.lower_bound(x);
           while(*ptr >= x && *ptr <= y && ptr != s.end()) {
               irene = a[*ptr] / k;
               Update(*ptr, irene - a[*ptr]);
               if(!irene) rmv.pb(*ptr);
               a[*ptr] = irene, ptr = next(ptr);
           }
           while(rmv.size()) s.erase(rmv.back()), rmv.pop_back();
        } else cout << Query(y) - Query(x - 1) << '\n';
    }
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 6 ms 636 KB Output is correct
12 Correct 6 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4728 KB Output is correct
2 Correct 48 ms 4268 KB Output is correct
3 Correct 61 ms 6904 KB Output is correct
4 Correct 78 ms 8568 KB Output is correct
5 Correct 88 ms 9176 KB Output is correct
6 Correct 87 ms 9184 KB Output is correct
7 Correct 88 ms 9080 KB Output is correct
8 Correct 86 ms 9080 KB Output is correct
9 Correct 193 ms 8952 KB Output is correct
10 Correct 87 ms 9080 KB Output is correct
11 Correct 85 ms 9024 KB Output is correct
12 Correct 85 ms 9016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1016 KB Output is correct
2 Correct 19 ms 2296 KB Output is correct
3 Correct 23 ms 2424 KB Output is correct
4 Correct 43 ms 1656 KB Output is correct
5 Correct 75 ms 4508 KB Output is correct
6 Correct 72 ms 4368 KB Output is correct
7 Correct 68 ms 5388 KB Output is correct
8 Correct 70 ms 5368 KB Output is correct
9 Correct 69 ms 5524 KB Output is correct
10 Correct 66 ms 5492 KB Output is correct
11 Correct 66 ms 5636 KB Output is correct
12 Correct 65 ms 5536 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3960 KB Output is correct
2 Correct 91 ms 3960 KB Output is correct
3 Correct 106 ms 3548 KB Output is correct
4 Correct 95 ms 2936 KB Output is correct
5 Correct 166 ms 7004 KB Output is correct
6 Correct 169 ms 6904 KB Output is correct
7 Correct 147 ms 7032 KB Output is correct
8 Correct 197 ms 7004 KB Output is correct
9 Correct 171 ms 7324 KB Output is correct
10 Correct 187 ms 7284 KB Output is correct
11 Correct 153 ms 7332 KB Output is correct
12 Correct 242 ms 7260 KB Output is correct