oj.uz

Submission #284552

# Submission time Handle Problem Language Result Execution time Memory
284552 2020-08-27T15:56:54 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 8080 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

template<typename T> struct segtree {
    
    T merge(T x, T y) {
	x += y;
	return x;
    }
    int n;
    vector<ll> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, T val) {
	if (tl == tr) {
	    t[v] = val;
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,val);
	    } else {
		upd(2*v+1,tm+1,tr,i,val);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return 0;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};

int n, q, k;
int a[maxn];
int S[maxn], T[maxn], U[maxn];

void brute(int type, int t, int u, ll& res) {
    if (type==1) {
	int idx = t;
	int val = u;
	a[idx] = val;
    }
    if (type==2) {
	int l = t;
	int r = u;
	for (int i=l; i<=r; i++) {
	    a[i] /= k;
	}
    }
    if (type==3) {
	res = 0;
	int l = t;
	int r = u;
	for (int i=l; i<=r; i++) {
	    res += a[i];
	}
    }
}


void solveTask3() {
    segtree<ll> tree;
    tree.init(n+10);
    for (int i=1; i<=n; i++) {
	tree.upd(1,1,n,i,a[i]);
    }
    for (int i=0; i<q; i++) {
	if (S[i]==1) {
	    tree.upd(1,1,n,T[i],U[i]);
	}
	if (S[i]==3) {
	    cout<<tree.qry(1,1,n,T[i],U[i])<<"\n";
	}
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q>>k;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=0; i<q; i++) {
	cin>>S[i]>>T[i]>>U[i];
    }

    if (k==1) {
	solveTask3();
	exit(0);
    }

    for (int i=0; i<q; i++) {
	int s = S[i];
	int t = T[i];
	int u = U[i];
	ll bans=-1; brute(s,t,u,bans);
	if (s==3) cout<<bans<<"\n";
    }
    
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 404 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 4092 KB Output is correct
2 Correct 49 ms 3320 KB Output is correct
3 Correct 51 ms 4472 KB Output is correct
4 Correct 66 ms 5880 KB Output is correct
5 Correct 77 ms 8056 KB Output is correct
6 Correct 78 ms 8056 KB Output is correct
7 Correct 77 ms 8080 KB Output is correct
8 Correct 84 ms 8056 KB Output is correct
9 Correct 76 ms 7928 KB Output is correct
10 Correct 74 ms 7928 KB Output is correct
11 Correct 74 ms 7928 KB Output is correct
12 Correct 74 ms 7928 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 1272 KB Output is correct
2 Correct 349 ms 1168 KB Output is correct
3 Correct 546 ms 1236 KB Output is correct
4 Correct 1194 ms 2040 KB Output is correct
5 Correct 4974 ms 2440 KB Output is correct
6 Correct 4955 ms 2696 KB Output is correct
7 Correct 68 ms 5624 KB Output is correct
8 Correct 4981 ms 2676 KB Output is correct
9 Execution timed out 5089 ms 3032 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 2180 KB Output is correct
2 Correct 2080 ms 2116 KB Output is correct
3 Correct 1103 ms 1784 KB Output is correct
4 Correct 1533 ms 2476 KB Output is correct
5 Correct 4941 ms 2572 KB Output is correct
6 Correct 4991 ms 2940 KB Output is correct
7 Execution timed out 5040 ms 4856 KB Time limit exceeded
8 Halted 0 ms 0 KB -