oj.uz

Submission #78927

# Submission time Handle Problem Language Result Execution time Memory
78927 2018-10-09T16:00:08 Z SpeedOfMagic Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2683 ms 202884 KB 
/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#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 << 1] += lazy[cur];
        lazy[cur << 1 | 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 << 1], right = segTree[cur << 1 | 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) >> 1;
        if (p <= mid) {
            updatePos(p, val, cur << 1, ll, mid);
            processLazy(cur << 1 | 1);
        } else {
            processLazy(cur << 1);
            updatePos(p, val, cur << 1 | 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) >> 1;
    spray(l, min(r, mid), cur << 1, ll, mid);
    spray(max(l, mid + 1), r, cur << 1 | 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) >> 1;
    return query(l, min(r, mid), cur << 1, ll, mid) + query(max(l, mid + 1), r, cur << 1 | 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 251 ms 177812 KB Output is correct
2 Correct 220 ms 178292 KB Output is correct
3 Correct 212 ms 178292 KB Output is correct
4 Correct 238 ms 178292 KB Output is correct
5 Correct 240 ms 178312 KB Output is correct
6 Correct 238 ms 178312 KB Output is correct
7 Correct 245 ms 178312 KB Output is correct
8 Correct 235 ms 178392 KB Output is correct
9 Correct 249 ms 178564 KB Output is correct
10 Correct 234 ms 178564 KB Output is correct
11 Correct 238 ms 178564 KB Output is correct
12 Correct 235 ms 178564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 193668 KB Output is correct
2 Correct 1118 ms 193668 KB Output is correct
3 Correct 1393 ms 195372 KB Output is correct
4 Correct 1668 ms 200108 KB Output is correct
5 Correct 1822 ms 202884 KB Output is correct
6 Correct 1934 ms 202884 KB Output is correct
7 Correct 1880 ms 202884 KB Output is correct
8 Correct 1871 ms 202884 KB Output is correct
9 Correct 1844 ms 202884 KB Output is correct
10 Correct 1827 ms 202884 KB Output is correct
11 Correct 1854 ms 202884 KB Output is correct
12 Correct 1885 ms 202884 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 202884 KB Output is correct
2 Correct 479 ms 202884 KB Output is correct
3 Correct 538 ms 202884 KB Output is correct
4 Correct 780 ms 202884 KB Output is correct
5 Correct 1183 ms 202884 KB Output is correct
6 Correct 1203 ms 202884 KB Output is correct
7 Correct 1813 ms 202884 KB Output is correct
8 Correct 1175 ms 202884 KB Output is correct
9 Correct 1158 ms 202884 KB Output is correct
10 Correct 1165 ms 202884 KB Output is correct
11 Correct 1144 ms 202884 KB Output is correct
12 Correct 1174 ms 202884 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 202884 KB Output is correct
2 Correct 1174 ms 202884 KB Output is correct
3 Correct 1170 ms 202884 KB Output is correct
4 Correct 1156 ms 202884 KB Output is correct
5 Correct 1607 ms 202884 KB Output is correct
6 Correct 1658 ms 202884 KB Output is correct
7 Correct 1817 ms 202884 KB Output is correct
8 Correct 2683 ms 202884 KB Output is correct
9 Correct 1690 ms 202884 KB Output is correct
10 Correct 2052 ms 202884 KB Output is correct
11 Correct 1474 ms 202884 KB Output is correct
12 Correct 2148 ms 202884 KB Output is correct