oj.uz

Submission #284624

# Submission time Handle Problem Language Result Execution time Memory
284624 2020-08-27T18:32:53 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 1565 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();
	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 41 ms 25464 KB Output is correct
2 Runtime error 771 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 798 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 170 ms 25592 KB Output is correct
2 Correct 124 ms 26360 KB Output is correct
3 Correct 178 ms 26528 KB Output is correct
4 Correct 453 ms 25976 KB Output is correct
5 Correct 657 ms 27528 KB Output is correct
6 Correct 680 ms 28152 KB Output is correct
7 Runtime error 619 ms 524288 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 656 ms 36380 KB Output is correct
2 Correct 742 ms 36256 KB Output is correct
3 Correct 776 ms 47608 KB Output is correct
4 Correct 875 ms 33272 KB Output is correct
5 Correct 1020 ms 46712 KB Output is correct
6 Correct 1090 ms 52472 KB Output is correct
7 Correct 1078 ms 49144 KB Output is correct
8 Correct 1565 ms 69704 KB Output is correct
9 Correct 1062 ms 53728 KB Output is correct
10 Correct 1293 ms 69348 KB Output is correct
11 Correct 938 ms 50844 KB Output is correct
12 Correct 1431 ms 77564 KB Output is correct