답안 #78927 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78927	2018-10-09T16:00:08 Z	SpeedOfMagic	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	2683 ms	202884 KB

sterilizing

/** 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #78927

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
75.0 / 75.0