답안 #78926 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78926	2018-10-09T15:52:02 Z	SpeedOfMagic	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	2833 ms	224644 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 * 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

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

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

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

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

답안 #78926

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