Submission #23026

#	Time	Username	Problem	Language	Result	Execution time	Memory
23026		shuuna	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	2343 ms	7848 KiB

sterilizing

//THIS IS ONLY TRIAL. SOLUTION FROM KAGAMIZ BLOG
#include <bits/stdc++.h>

#define MAX_N (100010)
#define MAX_Q (100010)
#define MAX_S (131072)

using namespace std;

typedef long long Int;

class BIT {
	Int A[MAX_N + 1];
public:
	BIT(){
		memset(A, 0, sizeof(A));
	}
	void add(int p, Int x){
		for (p++; p <= MAX_N; p += p & -p) A[p] += x;
	}
	Int sum(int p){
		Int ret = 0;
		for (p++; p; p &= (p - 1)) ret += A[p];
		return (ret);
	}
};

BIT bit;
int N, Q, K;
int C[MAX_N];
int S[MAX_Q], T[MAX_Q], U[MAX_Q];
pair<int, int> seg[2 * MAX_S - 1];

void update(int k, int x)
{
	k += MAX_S - 1;
    seg[k] = make_pair(x, k - MAX_S + 1);
    while (k){
        k = (k - 1) / 2;
        seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
}

pair<int, int> getMax(int a, int b, int k = 0, int l = 0, int r = MAX_S)
{
    if (b <= l || r <= a) return (make_pair(-1, -1));
    if (a <= l && r <= b) return (seg[k]);
    pair<int, int> lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2),
                   rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
    return (max(lch, rch));
}

void divide(int L, int R)
{
    if (L > R) return;
    pair<int, int> p = getMax(L, R + 1);
    if (p.first == 0) return;
    bit.add(p.second, -p.first);
    bit.add(p.second, p.first / K);
    C[p.second] /= K;
    update(p.second, C[p.second]);
    divide(L, p.second - 1);
    divide(p.second + 1, R);
}

int main()
{
	scanf("%d %d %d", &N, &Q, &K);

	for (int i = 0; i < N; i++){
		scanf("%d", C + i);
	}

	for (int i = 0; i < Q; i++){
		scanf("%d %d %d", S + i, T + i, U + i);
	}

	for (int i = 0; i < N; i++) bit.add(i, C[i]);
    for (int i = 0; i < MAX_S; i++) update(i, i < N ? C[i] : -1);

	for (int i = 0; i < Q; i++){
		if (S[i] == 1){
            update(T[i] - 1, U[i]);
			bit.add(T[i] - 1, (Int)U[i] - C[T[i] - 1]);
			C[T[i] - 1] = U[i];
		}
        else if (S[i] == 2){
            if (K == 1) continue;
            else divide(T[i] - 1, U[i] - 1);
        }
		else {
			printf("%lld\n", bit.sum(U[i] - 1) - bit.sum(T[i] - 2));
		}
	}

	return (0);
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:68:31: 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:71:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C + i);
                     ^
sterilizing.cpp:75:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", S + i, T + i, U + i);
                                         ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75