oj.uz

답안 #284623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284623 2020-08-27T18:31:05 Z limabeans Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 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;
	    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

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 25464 KB Output is correct
2 Runtime error 787 ms 524292 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 802 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 25848 KB Output is correct
2 Correct 452 ms 26488 KB Output is correct
3 Correct 664 ms 26744 KB Output is correct
4 Correct 1505 ms 27000 KB Output is correct
5 Execution timed out 5066 ms 28184 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2276 ms 37220 KB Output is correct
2 Correct 2669 ms 38136 KB Output is correct
3 Correct 1821 ms 48968 KB Output is correct
4 Correct 2336 ms 35312 KB Output is correct
5 Execution timed out 5066 ms 49192 KB Time limit exceeded
6 Halted 0 ms 0 KB -