oj.uz

Submission #23026

# Submission time Handle Problem Language Result Execution time Memory
23026 2017-05-01T23:47:18 Z shuuna Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 2343 ms 7848 KB 
//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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6412 KB Output is correct
2 Correct 19 ms 6412 KB Output is correct
3 Correct 26 ms 6412 KB Output is correct
4 Correct 49 ms 6412 KB Output is correct
5 Correct 49 ms 6412 KB Output is correct
6 Correct 39 ms 6412 KB Output is correct
7 Correct 46 ms 6412 KB Output is correct
8 Correct 46 ms 6412 KB Output is correct
9 Correct 59 ms 6412 KB Output is correct
10 Correct 46 ms 6412 KB Output is correct
11 Correct 43 ms 6412 KB Output is correct
12 Correct 46 ms 6412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6412 KB Output is correct
2 Correct 69 ms 6412 KB Output is correct
3 Correct 63 ms 6412 KB Output is correct
4 Correct 93 ms 6412 KB Output is correct
5 Correct 83 ms 6412 KB Output is correct
6 Correct 116 ms 6412 KB Output is correct
7 Correct 86 ms 6412 KB Output is correct
8 Correct 89 ms 6412 KB Output is correct
9 Correct 89 ms 6412 KB Output is correct
10 Correct 89 ms 6412 KB Output is correct
11 Correct 93 ms 6412 KB Output is correct
12 Correct 89 ms 6412 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6412 KB Output is correct
2 Correct 46 ms 6488 KB Output is correct
3 Correct 56 ms 6524 KB Output is correct
4 Correct 109 ms 6488 KB Output is correct
5 Correct 146 ms 6740 KB Output is correct
6 Correct 163 ms 6604 KB Output is correct
7 Correct 79 ms 6412 KB Output is correct
8 Correct 153 ms 6916 KB Output is correct
9 Correct 153 ms 7848 KB Output is correct
10 Correct 146 ms 7836 KB Output is correct
11 Correct 146 ms 7840 KB Output is correct
12 Correct 139 ms 7848 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 6412 KB Output is correct
2 Correct 536 ms 6412 KB Output is correct
3 Correct 1089 ms 6412 KB Output is correct
4 Correct 736 ms 6412 KB Output is correct
5 Correct 879 ms 6412 KB Output is correct
6 Correct 1133 ms 6412 KB Output is correct
7 Correct 789 ms 6412 KB Output is correct
8 Correct 1623 ms 6412 KB Output is correct
9 Correct 1239 ms 6424 KB Output is correct
10 Correct 1516 ms 6540 KB Output is correct
11 Correct 963 ms 6412 KB Output is correct
12 Correct 2343 ms 6420 KB Output is correct