oj.uz

Submission #694941

# Submission time Handle Problem Language Result Execution time Memory
694941 2023-02-04T13:52:44 Z Do_you_copy Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 183 ms 10224 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define int long long
using namespace std;
using ll = long long;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 +1;
const int inf = 0x3f3f3f3f;
//const int Mod =
int n, q, k;
ll bit[maxN];
map <int, int> mp;

void update(int x, int v){
    for (; x <= n; x += x & -x){
        bit[x] += v;
    }
}

int get(int x){
    int res = 0;
    for (; x; x -= x & -x){
        res += bit[x];
    }
    return res;
}


void Init(){
    cin >> n >> q >> k;
    for (int i = 1; i <= n; ++i){
        cin >> mp[i];
        update(i, mp[i]);
    }
    mp[n + 1] = 0;
    while (q--){
        int s, t, u;
        cin >> s >> t >> u;
        if (s == 1){
            update(t, u - mp[t]);
            mp[t] = u;
        }
        if (s == 2 && k != 1){
            for (auto it = mp.lower_bound(t); it->fi <= u;){
                auto it1 = it++;
                int x = it1->se;
                it1->se /= k;
                update(it1->fi, it1->se - x);
                if (it1->se == 0){
                    mp.erase(it1);
                }
            }
        }
        if (s == 3){
            cout << get(u) - get(t - 1) << "\n";
        }
    }
}

#define taskname "test"
signed main(){
    faster
    if (fopen(taskname ".inp", "r")){
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4324 KB Output is correct
2 Correct 43 ms 4588 KB Output is correct
3 Correct 57 ms 7644 KB Output is correct
4 Correct 84 ms 9712 KB Output is correct
5 Correct 83 ms 10196 KB Output is correct
6 Correct 84 ms 10188 KB Output is correct
7 Correct 95 ms 10224 KB Output is correct
8 Correct 83 ms 10188 KB Output is correct
9 Correct 79 ms 10048 KB Output is correct
10 Correct 82 ms 10156 KB Output is correct
11 Correct 79 ms 10060 KB Output is correct
12 Correct 82 ms 10060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 808 KB Output is correct
2 Correct 21 ms 3412 KB Output is correct
3 Correct 24 ms 3412 KB Output is correct
4 Correct 35 ms 2080 KB Output is correct
5 Correct 67 ms 7376 KB Output is correct
6 Correct 67 ms 7416 KB Output is correct
7 Correct 86 ms 8028 KB Output is correct
8 Correct 69 ms 8752 KB Output is correct
9 Correct 65 ms 8612 KB Output is correct
10 Correct 75 ms 8580 KB Output is correct
11 Correct 63 ms 8652 KB Output is correct
12 Correct 64 ms 8620 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4056 KB Output is correct
2 Correct 69 ms 5836 KB Output is correct
3 Correct 71 ms 4688 KB Output is correct
4 Correct 63 ms 4468 KB Output is correct
5 Correct 112 ms 10092 KB Output is correct
6 Correct 120 ms 10040 KB Output is correct
7 Correct 113 ms 10008 KB Output is correct
8 Correct 134 ms 10060 KB Output is correct
9 Correct 128 ms 9900 KB Output is correct
10 Correct 168 ms 9900 KB Output is correct
11 Correct 113 ms 9904 KB Output is correct
12 Correct 183 ms 10000 KB Output is correct