답안 #25133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25133 2017-06-20T07:49:59 Z 윤교준(#1055) Sterilizing Spray (JOI15_sterilizing) C++11
15 / 100
5000 ms 27880 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 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;
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() {
    scanf("%d%d%d", &N, &Q, &K);
    for(int i = 1, c; i <= N; i++) {
        scanf("%d", &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--;) {
        scanf("%d%d%d", &type, &a, &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:110:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &Q, &K);
                                ^
sterilizing.cpp:112:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &c);
                        ^
sterilizing.cpp:118:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &type, &a, &b);
                                       ^
# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 27880 KB Output is correct
2 Correct 0 ms 27880 KB Output is correct
3 Correct 9 ms 27880 KB Output is correct
4 Correct 63 ms 27880 KB Output is correct
5 Correct 96 ms 27880 KB Output is correct
6 Correct 79 ms 27880 KB Output is correct
7 Correct 109 ms 27880 KB Output is correct
8 Correct 79 ms 27880 KB Output is correct
9 Correct 89 ms 27880 KB Output is correct
10 Correct 76 ms 27880 KB Output is correct
11 Correct 79 ms 27880 KB Output is correct
12 Correct 83 ms 27880 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 27880 KB Output is correct
2 Correct 59 ms 27880 KB Output is correct
3 Correct 39 ms 27880 KB Output is correct
4 Correct 59 ms 27880 KB Output is correct
5 Correct 99 ms 27880 KB Output is correct
6 Correct 83 ms 27880 KB Output is correct
7 Correct 86 ms 27880 KB Output is correct
8 Correct 79 ms 27880 KB Output is correct
9 Correct 83 ms 27880 KB Output is correct
10 Correct 73 ms 27880 KB Output is correct
11 Correct 89 ms 27880 KB Output is correct
12 Correct 63 ms 27880 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1319 ms 27880 KB Output is correct
2 Correct 723 ms 27880 KB Output is correct
3 Correct 1259 ms 27880 KB Output is correct
4 Correct 3586 ms 27880 KB Output is correct
5 Execution timed out 5000 ms 27880 KB Execution timed out
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2853 ms 27880 KB Output is correct
2 Correct 3253 ms 27880 KB Output is correct
3 Correct 2259 ms 27880 KB Output is correct
4 Correct 4143 ms 27880 KB Output is correct
5 Execution timed out 5000 ms 27880 KB Execution timed out
6 Halted 0 ms 0 KB -