Submission #284628

#	Time	Username	Problem	Language	Result	Execution time	Memory
284628		limabeans	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	1537 ms	75384 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;

int n, q, k;

struct node {
    int ptr;
    vector<ll> versions;
    node() {
	ptr=0;
	versions = {0};
    }
    node(ll val) {
	ptr=0;
	versions.clear();
	if (k==1) {
	    versions = {val};
	} else {
	    while (val>0) {
		versions.push_back(val);
		val/=k;
	    }
	    versions.push_back(0);
	}
    }
    void incr() {
	ptr++;
    }
    ll get(int offset) {
	int len = versions.size();
	return versions[min(len-1, ptr+offset)];
    }
};

ll a[maxn];
node t[4*maxn];
int mark[4*maxn];

node merge(node left, node right) {
    vector<ll> versions;
    if (k==1) {
	versions.push_back(left.get(0) + right.get(0));
    } else {
	for (int o=0; ; o++) {
	    ll L = left.get(o);
	    ll R = right.get(o);
	    versions.push_back(L+R);
	    if (L+R==0) break;
	}
    }
    node res;
    res.ptr = 0;
    res.versions = versions;
    return res;
}

void build(int v, int tl, int tr) {
    if (tl==tr) {
	t[v] = node(a[tl]);
    } else {
	int tm=(tl+tr)/2;
	build(2*v,tl,tm);
	build(2*v+1,tm+1,tr);
	t[v]=merge(t[v*2],t[v*2+1]);
    }
}

void push(int v) {
    if (mark[v]>0) {
	mark[2*v] += mark[v];
	mark[2*v+1] += mark[v];
	while (mark[v]>0) {
	    t[2*v].incr();
	    t[2*v+1].incr();
	    mark[v]--;
	}
    }
}

void upd(int v, int tl, int tr, int i, ll val) {
    if (tl==tr) {
	t[v] = node(val);
    } else {
	push(v);
	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[v*2],t[v*2+1]);
    }
}

void spray(int v, int tl, int tr, int l, int r) {
    if (l>r) return;
    if (l==tl && tr==r) {
	t[v].incr();
	mark[v]++;
	return;
    }
    push(v);
    int tm=(tl+tr)/2;
    spray(2*v,tl,tm,l,min(tm,r));
    spray(2*v+1,tm+1,tr,max(tm+1,l),r);
    t[v]=merge(t[v*2],t[v*2+1]);
}


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


void setValue(int i, ll val) {
    upd(1,1,n,i,val);
}

void spray(int l, int r) {
    spray(1,1,n,l,r);
}


ll rangeSum(int l, int r) {
    return qry(1,1,n,l,r);
}


void print() {
    cout<<"tree"<<endl;
    for (int i=1; i<=n; i++) {
	cout<<rangeSum(i,i)<<" ";
    }
    cout<<endl;
    for (int i=1; i<=n; i++) {
	cout<<a[i]<<" ";
    }
    cout<<endl;
    for (int i=1; i<=9; i++) {
	cout<<t[i].get(0)<<" ";
    }
    cout<<endl;
    for (int i=1; i<=9; i++) {
	cout<<mark[i]<<" ";
    }
    cout<<endl;
    cout<<endl;
}

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];
    }
    build(1,1,n);


    //print();

    while (q--) {
	int type;
	cin>>type;
	if (type==1) {
	    int i, val;
	    cin>>i>>val;
	    setValue(i, val);

	    //a[i]=val;
	}
	if (type==2) {
	    int l, r;
	    cin>>l>>r;

	    if (k>1) {
		spray(l,r);
	    }

	    // for (int i=l; i<=r; i++) {
	    // 	a[i] /= k;
	    // }
	}
	if (type==3) {
	    int l, r;
	    cin>>l>>r;
	    cout<<rangeSum(l,r)<<"\n";
	}
	//print();
	
    }
    
    
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75