Submission #284588

#	Time	Username	Problem	Language	Result	Execution time	Memory
284588		limabeans	Sterilizing Spray (JOI15_sterilizing)	C++17	25 / 100	192 ms	7416 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 = 1e5 + 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 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";
    }
}

// Task2 on oj.uz
void solveTask2() {
    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";
	}
    }
}

//////////////////////////////////////////////////////////////////
ll t[4*maxn];
ll mark[4*maxn];

const int NONE = -1;

void push(int v, int tl, int tr) {
    if (mark[v]!=NONE) {
	int tm=(tl+tr)/2;
	t[2*v]=1ll*(tm-tl+1)*mark[v];
	t[2*v+1]=1ll*(tr-tm)*mark[v];
	mark[v*2]=mark[2*v+1]=mark[v];
	mark[v]=NONE;
    }
}

// ll queryRange(int v, int tl, int tr, int l, int r) {
//     if (l>r) return 0;
//     if (l==tl && tr==r) {
// 	return t[v];
//     }
//     push(v,tl,tr);
//     int tm=(tl+tr)/2;
//     return queryRange(2*v,tl,tm,l,min(tm,r))
// 	+  queryRange(2*v+1,tm+1,tr,max(tm+1,l),r);
// }

ll queryRange(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];
    push(v,tl,tr);
    int tm=(tl+tr)/2;
    return queryRange(2*v,tl,tm,l,r)+queryRange(2*v+1,tm+1,tr,l,r);
}

void setRange(int v, int tl, int tr, int l, int r, int val) {
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
	t[v]=1ll*(tr-tl+1)*val;
	mark[v]=val;
	return;
    }
    push(v,tl,tr);
    int tm=(tl+tr)/2;
    setRange(2*v,tl,tm,l,r,val);
    setRange(2*v+1,tm+1,tr,l,r,val);
    t[v]=t[2*v]+t[2*v+1];
    
}
// void setRange(int v, int tl, int tr, int l, int r, int val) {
//     if (l>r) return;
//     if (l==tl && tr==r) {
// 	t[v]=1ll*(tr-tl+1)*val;
// 	mark[v]=val;
// 	return;
//     }
//     push(v,tl,tr);
//     int tm=(tl+tr)/2;
//     setRange(2*v,tl,tm,l,min(tm,r),val);
//     setRange(2*v+1,tm+1,tr,max(tm+1,l),r,val);
//     t[v]=t[2*v]+t[2*v+1];
// }

//////////////////////////////////////////////////////////////////

void solveTask3() {
    //cout<<"Task3"<<endl;
    bool check = false;
    for (int i=1; i<=n; i++) {
	setRange(1,1,n,i,i,a[i]);
    }

    for (int i=0; i<q; i++) {
	ll bans=-1;
	if (check) {
	    brute(S[i],T[i],U[i],bans);
	}
	
	if (S[i]==1) {
	    setRange(1,1,n,T[i],T[i],U[i]);
	}
	if (S[i]==2) {
	    if (k>1) {
		setRange(1,1,n,T[i],U[i],0);
	    }
	}
	if (S[i]==3) {
	    ll res = queryRange(1,1,n,T[i],U[i]);
	    if (check) {
		cout<<res<<" "<<bans<<endl;
		assert(res==bans);
	    }
	    cout<<res<<endl;
	}
    }
}


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

    cin>>n>>q>>k;
    bool isTask3 = true;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
	if (!(0<=a[i] && a[i]<=1)) isTask3=false;
    }
    for (int i=0; i<q; i++) {
	cin>>S[i]>>T[i]>>U[i];
	if (S[i]==1) {
	    if (!(0<=U[i] && U[i]<=1)) isTask3=false;
	}
    }

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

    if (isTask3) {
	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: 10 / 10
• Subtask 4: 0 / 75