oj.uz

Submission #521380

# Submission time Handle Problem Language Result Execution time Memory
521380 2022-02-02T02:28:52 Z perchuts Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 1345 ms 202892 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
/* Solution:
1. Obviously it can be solved by lazy segment tree.
2. Each node keeps 2 elements: lazy (how much time I need to spray) and queue,
where future values after each spray are stored.
3. For each spray, I just pop element from queue and process this like a normal lazy segment tree.
4. If I need to update element on position, I just rewrite all queues on path from root to position.
5. If k = 1, then I ignore second query and limit queue size to log(MAX_A) = 30.
Time complexity: O(n + q * log(MAX_N) * log(MAX_A)). Memory: O(n * log(MAX_A)).
*/
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
//template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void println(){eol;} template<typename Arg,typename... Args> void println(Arg  arg,Args...  args){put (arg)<<" ";println(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const int N = 131072;
const int LIM = 30;
queue<long long> segTree[N * 2];
int lazy[N * 2];
int k;
 
inline long long front(queue<long long>& cur) { return (cur.empty() ? 0ll : cur.front()); }
 
inline void processLazy(int cur) {
    if (cur < N) {
        lazy[cur * 2] += lazy[cur];
        lazy[cur * 2 + 1] += lazy[cur];
    }
 
    for (; lazy[cur] && !segTree[cur].empty(); lazy[cur]--)
        segTree[cur].pop();
 
    lazy[cur] = 0;
}
 
inline void updateElement(int cur) {
    queue<long long> left = segTree[cur * 2], right = segTree[cur * 2 + 1];
    if (sz(left) < sz(right))
        swap(left, right);
 
    while (!segTree[cur].empty())
        segTree[cur].pop();
 
    while (!left.empty()) {
        segTree[cur].push(front(left) + front(right));
        left.pop();
        if (!right.empty())
            right.pop();
    }
}
 
 
inline void updatePos(int p, long long val, int cur = 1, int ll = 1, int rr = N) {
    processLazy(cur);
    if (ll != rr) {
        int mid = (ll + rr) / 2;
        if (p <= mid) {
            updatePos(p, val, cur * 2, ll, mid);
            processLazy(cur * 2 + 1);
        } else {
            processLazy(cur * 2);
            updatePos(p, val, cur * 2 + 1, mid + 1, rr);
        }
 
        updateElement(cur);
    } else {
        while (!segTree[cur].empty())
            segTree[cur].pop();
 
        for (; val && sz(segTree[cur]) < LIM; val /= k)
            segTree[cur].push(val);
    }
}
 
inline void spray(int l, int r, int cur = 1, int ll = 1, int rr = N) {
    if (k == 1)
        return;
    //debug(l, r, cur, ll, rr);
    if (l == ll && r == rr) 
        lazy[cur]++;
    
 
    processLazy(cur);
    if (l > r || (l == ll && r == rr))
        return;
 
    int mid = (ll + rr) / 2;
    spray(l, min(r, mid), cur * 2, ll, mid);
    spray(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr);
    updateElement(cur);
}
 
inline long long query(int l, int r, int cur = 1, int ll = 1, int rr = N) {
    processLazy(cur);
    if (l > r)
        return 0;
    if (l == ll && r == rr)
        return front(segTree[cur]);
    int mid = (ll + rr) / 2;
    return query(l, min(r, mid), cur * 2, ll, mid) + query(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr);
}
 
void run() {
    int n, q;
    read(n, q, k);
 
    rep(i, 0, n)
        updatePos(i + 1, getInt());

  	rep(i, 0, 2 * N)
      	lazy[i] = 0;

    for (; q; q--) {
        int s, t, u;
        read(s, t, u);
        if (s == 1)
            updatePos(t, u);
        else if (s == 2)
            spray(t, u);
        else
            put query(t, u), eol;
    }
}
 
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 177804 KB Output is correct
2 Correct 119 ms 178016 KB Output is correct
3 Correct 110 ms 177788 KB Output is correct
4 Correct 139 ms 177992 KB Output is correct
5 Correct 141 ms 177928 KB Output is correct
6 Correct 144 ms 178088 KB Output is correct
7 Correct 138 ms 177860 KB Output is correct
8 Correct 137 ms 177896 KB Output is correct
9 Correct 141 ms 178200 KB Output is correct
10 Correct 144 ms 178032 KB Output is correct
11 Correct 134 ms 177860 KB Output is correct
12 Correct 138 ms 177844 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 193336 KB Output is correct
2 Correct 685 ms 189652 KB Output is correct
3 Correct 850 ms 195256 KB Output is correct
4 Correct 1027 ms 200396 KB Output is correct
5 Correct 1137 ms 202824 KB Output is correct
6 Correct 1129 ms 202792 KB Output is correct
7 Correct 1143 ms 202692 KB Output is correct
8 Correct 1146 ms 202892 KB Output is correct
9 Correct 1148 ms 202640 KB Output is correct
10 Correct 1127 ms 202692 KB Output is correct
11 Correct 1142 ms 202740 KB Output is correct
12 Correct 1170 ms 202740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 177852 KB Output is correct
2 Correct 287 ms 178168 KB Output is correct
3 Correct 311 ms 178156 KB Output is correct
4 Correct 475 ms 177956 KB Output is correct
5 Correct 717 ms 178576 KB Output is correct
6 Correct 722 ms 178744 KB Output is correct
7 Correct 1075 ms 194808 KB Output is correct
8 Correct 720 ms 178768 KB Output is correct
9 Correct 696 ms 178728 KB Output is correct
10 Correct 686 ms 178708 KB Output is correct
11 Correct 702 ms 178872 KB Output is correct
12 Correct 682 ms 178600 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 179456 KB Output is correct
2 Correct 676 ms 182188 KB Output is correct
3 Correct 725 ms 180600 KB Output is correct
4 Correct 722 ms 178904 KB Output is correct
5 Correct 958 ms 180036 KB Output is correct
6 Correct 1006 ms 179656 KB Output is correct
7 Correct 938 ms 188404 KB Output is correct
8 Correct 1202 ms 194528 KB Output is correct
9 Correct 1069 ms 185984 KB Output is correct
10 Correct 1135 ms 194460 KB Output is correct
11 Correct 917 ms 183564 KB Output is correct
12 Correct 1345 ms 196176 KB Output is correct