oj.uz

Submission #284626

# Submission time Handle Problem Language Result Execution time Memory
284626 2020-08-27T18:35:35 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 1531 ms 524292 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 = 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;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 25464 KB Output is correct
2 Runtime error 701 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 702 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 25592 KB Output is correct
2 Correct 129 ms 26360 KB Output is correct
3 Correct 164 ms 26404 KB Output is correct
4 Correct 436 ms 26104 KB Output is correct
5 Correct 639 ms 27512 KB Output is correct
6 Correct 646 ms 27512 KB Output is correct
7 Runtime error 698 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 36472 KB Output is correct
2 Correct 789 ms 36472 KB Output is correct
3 Correct 783 ms 47736 KB Output is correct
4 Correct 939 ms 33400 KB Output is correct
5 Correct 1038 ms 46872 KB Output is correct
6 Correct 1095 ms 50104 KB Output is correct
7 Correct 1022 ms 46844 KB Output is correct
8 Correct 1531 ms 67192 KB Output is correct
9 Correct 1064 ms 51832 KB Output is correct
10 Correct 1301 ms 67332 KB Output is correct
11 Correct 1006 ms 48760 KB Output is correct
12 Correct 1473 ms 75640 KB Output is correct