oj.uz

Submission #25134

# Submission time Handle Problem Language Result Execution time Memory
25134 2017-06-20T07:52:17 Z 윤교준(#1055) Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 4789 ms 33252 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (100005)
#define SQN (333)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static unsigned char str[5500055], *p=str;
struct BUC {
    ll Y[MAXN][31];
    ll sum[MAXN/SQN+5][31];
    int sumidx[MAXN/SQN+5];

    int getIdx(int X) { return (X-1)/SQN + 1; }
    int getSidx(int idx) { return (idx-1)*SQN + 1; }
    int getEidx(int idx) { return idx*SQN; }
    void rotY(int X, int cnt = 1) {
        if(!cnt) return; if(31 < cnt) cnt = 31;
        for(int i = cnt; i < 31; i++) Y[X][i-cnt] = Y[X][i];
        for(int i = 31-cnt; i < 31; i++) Y[X][i] = 0;
    }
    void updBuc(int idx) {
        const int S = getSidx(idx), E = getEidx(idx);
        for(int i = S; i <= E; i++) rotY(i, sumidx[idx]);
        sumidx[idx] = 0; fill(sum[idx], sum[idx]+31, 0);
        for(int i = S; i <= E; i++) for(int j = 0; j < 31; j++)
            sum[idx][j] += Y[i][j];
    }
    void update(int S, int E) {
        const int Sidx = getIdx(S), Eidx = getIdx(E);
        if(Sidx == Eidx) {
            for(int i = S; i <= E; i++) rotY(i);
            updBuc(Sidx);
        } else {
            for(int i = Sidx+1; i < Eidx; i++) sumidx[i]++;
            for(int i = Sidx+1; i < Eidx; i++) if(30 < sumidx[i]) sumidx[i] = 30;
            for(int i = getEidx(Sidx); S <= i; i--) rotY(i);
            for(int i = getSidx(Eidx); i <= E; i++) rotY(i);
            updBuc(Sidx); updBuc(Eidx);
        }
    }
    void __insert(int X, int R, int K) {
        for(int i = 0; i < 31; R /= K, i++) Y[X][i] = R;
    }
    void insert(int X, int R, int K) {
        updBuc(getIdx(X));
        __insert(X, R, K);
        updBuc(getIdx(X));
    }
    void __updateall(int N) {
        for(int i = getIdx(N); i; i--) updBuc(i);
    }
    ll getSum(int S, int E) {
        const int Sidx = getIdx(S), Eidx = getIdx(E);
        ll ret = 0;
        if(Sidx == Eidx) {
            updBuc(Sidx);
            for(int i = S; i <= E; i++) ret += Y[i][0];
        } else {
            updBuc(Sidx); updBuc(Eidx);
            for(int i = Sidx+1; i < Eidx; i++) ret += sum[i][sumidx[i]];
            for(int i = getEidx(Sidx); S <= i; i--) ret += Y[i][0];
            for(int i = getSidx(Eidx); i <= E; i++) ret += Y[i][0];
        }
        return ret;
    }
};
struct BIT {
    ll d[MAXN], v[MAXN];
    void _upd(int i, ll r) { for(; i < MAXN; i += rb(i)) d[i] += r; }
    void upd(int i, int r) { _upd(i, (ll)r-v[i]); v[i] = r; }
    ll get(int i) {
        ll r = 0; for(; i; i -= rb(i)) r += d[i];
        return r;
    }
    ll get(int s, int e) { return get(e) - get(s-1); }
};

BUC BT;
BIT ST;
int N, Q, K;

int main() {
    fread(str, 1, 5500055, stdin);
    rf(N) rf(Q) rf(K)
    for(int i = 1, c; i <= N; i++) {
        rf(c)
        if(1 == K) ST.upd(i, c);
        else BT.__insert(i, c, K);
    }
    if(1 != K) BT.__updateall(N);
    for(int type, a, b; Q--;) {
        rf(type) rf(a) rf(b)
        if(1 == type) {
            if(1 == K) ST.upd(a, b);
            else BT.insert(a, b, K);
        } else if(2 == type) {
            if(1 != K) BT.update(a, b);
        } else {
            printf("%lld\n", (1 == K) ? ST.get(a, b) : BT.getSum(a, b));
        }
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:112:34: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(str, 1, 5500055, stdin);
                                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33252 KB Output is correct
2 Correct 0 ms 33252 KB Output is correct
3 Correct 3 ms 33252 KB Output is correct
4 Correct 53 ms 33252 KB Output is correct
5 Correct 73 ms 33252 KB Output is correct
6 Correct 63 ms 33252 KB Output is correct
7 Correct 66 ms 33252 KB Output is correct
8 Correct 83 ms 33252 KB Output is correct
9 Correct 73 ms 33252 KB Output is correct
10 Correct 73 ms 33252 KB Output is correct
11 Correct 89 ms 33252 KB Output is correct
12 Correct 86 ms 33252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 33252 KB Output is correct
2 Correct 13 ms 33252 KB Output is correct
3 Correct 16 ms 33252 KB Output is correct
4 Correct 19 ms 33252 KB Output is correct
5 Correct 16 ms 33252 KB Output is correct
6 Correct 19 ms 33252 KB Output is correct
7 Correct 13 ms 33252 KB Output is correct
8 Correct 16 ms 33252 KB Output is correct
9 Correct 13 ms 33252 KB Output is correct
10 Correct 13 ms 33252 KB Output is correct
11 Correct 13 ms 33252 KB Output is correct
12 Correct 16 ms 33252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1219 ms 33252 KB Output is correct
2 Correct 699 ms 33252 KB Output is correct
3 Correct 1029 ms 33252 KB Output is correct
4 Correct 3539 ms 33252 KB Output is correct
5 Correct 4756 ms 33252 KB Output is correct
6 Correct 4343 ms 33252 KB Output is correct
7 Correct 9 ms 33252 KB Output is correct
8 Correct 4346 ms 33252 KB Output is correct
9 Correct 2979 ms 33252 KB Output is correct
10 Correct 3316 ms 33252 KB Output is correct
11 Correct 3129 ms 33252 KB Output is correct
12 Correct 3203 ms 33252 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2819 ms 33252 KB Output is correct
2 Correct 3633 ms 33252 KB Output is correct
3 Correct 2099 ms 33252 KB Output is correct
4 Correct 3386 ms 33252 KB Output is correct
5 Correct 4053 ms 33252 KB Output is correct
6 Correct 4463 ms 33252 KB Output is correct
7 Correct 4763 ms 33252 KB Output is correct
8 Correct 4789 ms 33252 KB Output is correct
9 Correct 3106 ms 33252 KB Output is correct
10 Correct 2909 ms 33252 KB Output is correct
11 Correct 2933 ms 33252 KB Output is correct
12 Correct 2956 ms 33252 KB Output is correct