oj.uz

답안 #25132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25132 2017-06-20T07:47:13 Z 윤교준(#1055) Sterilizing Spray (JOI15_sterilizing) C++11
15 / 100
 2939 ms 27096 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][30];
    ll sum[MAXN/SQN+5][30];
    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(30 < cnt) cnt = 30;
        for(int i = cnt; i < 30; i++) Y[X][i-cnt] = Y[X][i];
        for(int i = 30-cnt; i < 30; 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]+30, 0);
        for(int i = S; i <= E; i++) for(int j = 0; j < 30; 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 = 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 < 30; 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:109: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:111:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &c);
                        ^
sterilizing.cpp:117: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);
                                       ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 27096 KB Output is correct
2 Correct 0 ms 27096 KB Output is correct
3 Correct 6 ms 27096 KB Output is correct
4 Correct 59 ms 27096 KB Output is correct
5 Correct 83 ms 27096 KB Output is correct
6 Correct 76 ms 27096 KB Output is correct
7 Correct 83 ms 27096 KB Output is correct
8 Correct 73 ms 27096 KB Output is correct
9 Correct 83 ms 27096 KB Output is correct
10 Correct 76 ms 27096 KB Output is correct
11 Correct 73 ms 27096 KB Output is correct
12 Correct 76 ms 27096 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 27096 KB Output is correct
2 Correct 43 ms 27096 KB Output is correct
3 Correct 66 ms 27096 KB Output is correct
4 Correct 83 ms 27096 KB Output is correct
5 Correct 109 ms 27096 KB Output is correct
6 Correct 73 ms 27096 KB Output is correct
7 Correct 86 ms 27096 KB Output is correct
8 Correct 99 ms 27096 KB Output is correct
9 Correct 83 ms 27096 KB Output is correct
10 Correct 93 ms 27096 KB Output is correct
11 Correct 59 ms 27096 KB Output is correct
12 Correct 83 ms 27096 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1183 ms 27096 KB Output is correct
2 Incorrect 669 ms 27096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2939 ms 27096 KB Output isn't correct
2 Halted 0 ms 0 KB -