Submission #284554

#	Time	Username	Problem	Language	Result	Execution time	Memory
284554		limabeans	Sterilizing Spray (JOI15_sterilizing)	C++17	15 / 100	89 ms	5752 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75