oj.uz

Submission #284554

# Submission time Handle Problem Language Result Execution time Memory
284554 2020-08-27T15:59:09 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 89 ms 5752 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";
	}
    }
}

void solveTask1() {
    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";
    }
}

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);
    }

    if (n<=3000 && q<=3000) {
	solveTask1();
	exit(0);
    }

    assert(false);
    
    
    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 416 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 7 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3704 KB Output is correct
2 Correct 61 ms 3084 KB Output is correct
3 Correct 52 ms 4216 KB Output is correct
4 Correct 66 ms 5228 KB Output is correct
5 Correct 78 ms 5752 KB Output is correct
6 Correct 77 ms 5624 KB Output is correct
7 Correct 79 ms 5600 KB Output is correct
8 Correct 76 ms 5500 KB Output is correct
9 Correct 73 ms 5624 KB Output is correct
10 Correct 89 ms 5624 KB Output is correct
11 Correct 71 ms 5560 KB Output is correct
12 Correct 72 ms 5628 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 1536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 2568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -