oj.uz

Submission #78926

# Submission time Handle Problem Language Result Execution time Memory
78926 2018-10-09T15:52:02 Z SpeedOfMagic Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 2833 ms 224644 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 * 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 215 ms 177784 KB Output is correct
2 Correct 196 ms 178164 KB Output is correct
3 Correct 204 ms 178164 KB Output is correct
4 Correct 227 ms 178556 KB Output is correct
5 Correct 227 ms 178556 KB Output is correct
6 Correct 234 ms 178656 KB Output is correct
7 Correct 233 ms 178656 KB Output is correct
8 Correct 237 ms 178656 KB Output is correct
9 Correct 244 ms 178924 KB Output is correct
10 Correct 236 ms 178924 KB Output is correct
11 Correct 247 ms 178924 KB Output is correct
12 Correct 240 ms 178924 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1362 ms 194428 KB Output is correct
2 Correct 1139 ms 194428 KB Output is correct
3 Correct 1386 ms 199496 KB Output is correct
4 Correct 1682 ms 206196 KB Output is correct
5 Correct 2015 ms 211264 KB Output is correct
6 Correct 1963 ms 213700 KB Output is correct
7 Correct 1981 ms 216176 KB Output is correct
8 Correct 1909 ms 218492 KB Output is correct
9 Correct 1920 ms 220668 KB Output is correct
10 Correct 2035 ms 223116 KB Output is correct
11 Correct 1993 ms 224644 KB Output is correct
12 Correct 1961 ms 224644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 224644 KB Output is correct
2 Correct 486 ms 224644 KB Output is correct
3 Correct 545 ms 224644 KB Output is correct
4 Correct 840 ms 224644 KB Output is correct
5 Correct 1230 ms 224644 KB Output is correct
6 Correct 1259 ms 224644 KB Output is correct
7 Correct 1963 ms 224644 KB Output is correct
8 Correct 1261 ms 224644 KB Output is correct
9 Correct 1176 ms 224644 KB Output is correct
10 Correct 1186 ms 224644 KB Output is correct
11 Correct 1172 ms 224644 KB Output is correct
12 Correct 1153 ms 224644 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1103 ms 224644 KB Output is correct
2 Correct 1167 ms 224644 KB Output is correct
3 Correct 1184 ms 224644 KB Output is correct
4 Correct 1202 ms 224644 KB Output is correct
5 Correct 1695 ms 224644 KB Output is correct
6 Correct 1798 ms 224644 KB Output is correct
7 Correct 1752 ms 224644 KB Output is correct
8 Correct 2833 ms 224644 KB Output is correct
9 Correct 1757 ms 224644 KB Output is correct
10 Correct 2246 ms 224644 KB Output is correct
11 Correct 1546 ms 224644 KB Output is correct
12 Correct 2299 ms 224644 KB Output is correct