oj.uz

Submission #25104

# Submission time Handle Problem Language Result Execution time Memory
25104 2017-06-20T06:57:18 Z 윤교준(#1055) Sterilizing Spray (JOI15_sterilizing) C++11
5 / 100
 5000 ms 3588 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 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 dt[MAXN];
    ll sum[MAXN/SQN + 5], div[MAXN/SQN + 5];

    void init() { fill(div, div+(MAXN/SQN + 5), 1); }
    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 updiv(int idx, ll R) { div[idx] *= R; if(INF < div[idx]) div[idx] = (ll)INF*4; }
    void updBuc(int idx) {
        const int S = getSidx(idx), E = getEidx(idx);
        ll &ret = sum[idx]; ret = 0;
        for(int i = S; i <= E; i++) {
            dt[i] /= div[idx]; ret += dt[i];
        }
        div[idx] = 1;
    }
    void update(int S, int E, ll R) {
        const int Sidx = getIdx(S), Eidx = getIdx(E);
        for(int i = Sidx+1; i < Eidx; i++) {
            updiv(i, R); sum[i] /= R;
        }
        if(Sidx == Eidx) {
            updBuc(Sidx); for(int i = S; i <= E; i++) dt[i] /= R;
            updBuc(Sidx);
        } else {
            updBuc(Sidx); updBuc(Eidx);
            for(int i = getEidx(Sidx); S <= i; i--) dt[i] /= R;
            for(int i = getSidx(Eidx); i <= E; i++) dt[i] /= R;
            updBuc(Sidx); updBuc(Eidx);
        }
    }
    void insert(int X, int R) {
        const int idx = getIdx(X);
        updBuc(idx); dt[X] = R; updBuc(idx);
    }
    ll getSum(int S, int E) {
        const int Sidx = getIdx(S), Eidx = getIdx(E);
        ll ret = 0;
        for(int i = Sidx+1; i < Eidx; i++) ret += sum[i];
        updBuc(Sidx); if(Sidx != Eidx) updBuc(Eidx);
        if(Sidx == Eidx) {
            for(int i = S; i <= E; i++) ret += dt[i];
        } else {
            for(int i = getEidx(Sidx); S <= i; i--) ret += dt[i];
            for(int i = getSidx(Eidx); i <= E; i++) ret += dt[i];
        }
        return ret;
    }
};

BUC BT;
int N, Q, K;

ll A[MAXN];

int main() {
    BT.init();
    scanf("%d%d%d", &N, &Q, &K);
    for(int i = 1, c; i <= N; i++) {
        scanf("%d", &c); //BT.dt[i] = c; BT.sum[BT.getIdx(i)] += c;
        A[i] = c;
    }
    for(int type, a, b; Q--;) {
        scanf("%d%d%d", &type, &a, &b);
        if(1 == type) A[a] = b;
        else if(2 == type) {
            for(int i = a; i <= b; i++) A[i] /= K;
        } else {
            ll ret = 0;
            for(int i = a; i <= b; i++) ret += A[i];
            printf("%lld\n", ret);
        }
        /*
        if(1 == type) BT.insert(a, b);
        else if(2 == type) BT.update(a, b, K);
        else printf("%lld\n", BT.getSum(a, b));
        */
    }
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:92: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:94:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &c); //BT.dt[i] = c; BT.sum[BT.getIdx(i)] += c;
                        ^
sterilizing.cpp:98: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

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 3588 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 3588 KB Output is correct
2 Correct 796 ms 3588 KB Output is correct
3 Correct 1243 ms 3588 KB Output is correct
4 Correct 2696 ms 3588 KB Output is correct
5 Execution timed out 5000 ms 3588 KB Execution timed out
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3753 ms 3588 KB Output is correct
2 Correct 4409 ms 3588 KB Output is correct
3 Correct 2426 ms 3588 KB Output is correct
4 Correct 3289 ms 3588 KB Output is correct
5 Execution timed out 5000 ms 3588 KB Execution timed out
6 Halted 0 ms 0 KB -