oj.uz

Submission #80504

# Submission time Handle Problem Language Result Execution time Memory
80504 2018-10-21T04:09:42 Z AngelKnows Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 3281 ms 354524 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define sz(x) ((int)(x).size())
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const double eps=1e-5;
const int mo=1e9+7;

int n,q,KK;
int tag[4*N];
queue<ll> seg[4*N];
void down(int k,int l,int r) {
	int cnt=tag[k];
	while ((int)seg[k].size()&&cnt>0) {
		seg[k].pop();
		cnt--;
	}
	if (l==r) {
		tag[k]=0;
		return;
	}
	tag[k<<1]+=tag[k];
	tag[k<<1|1]+=tag[k];
	tag[k]=0;
}
ll get(queue<ll> &a) {
	if (a.size()) return a.front();
	else return 0;
}
void update(int k,int l,int r) {
	while (seg[k].size()) {
		seg[k].pop();
	}
	if (l==r) return;
	queue<ll> a=seg[k<<1],b=seg[k<<1|1];
	if ((int)a.size()<(int)b.size()) swap(a,b);
	while (a.size()) {
		seg[k].push(get(a)+get(b));
		a.pop();
		if (b.size()) {
			b.pop();	
		}
	}
}
void change(int k,int l,int r,int x,int v) {
	if (l==r) {
		tag[k]=0;
		while (seg[k].size()) seg[k].pop();
		while (v) {
			seg[k].push(v);
			v/=KK;
			if (KK==1) break;
		}
	} else {
		down(k,l,r);
		int mid=(l+r)>>1;
		if (x<=mid) {
			change(k<<1,l,mid,x,v);
			down(k<<1|1,mid+1,r);
		} else {
			change(k<<1|1,mid+1,r,x,v);
			down(k<<1,l,mid);
		}
		update(k,l,r);
	}
}
void spray(int k,int L,int R,int l,int r) {
	down(k,L,R);
	if (l==L&&r==R) {
		if (seg[k].size()) seg[k].pop();
		if (l!=r) {
			tag[k<<1]++;
			tag[k<<1|1]++;
		}
		return;
	}
	int mid=(L+R)>>1;
	if (r<=mid) {
		spray(k<<1,L,mid,l,r);
		down(k<<1|1,mid+1,R);
		update(k,L,R);
	} else if (l>mid) {
		spray(k<<1|1,mid+1,R,l,r);
		down(k<<1,L,mid);
		update(k,L,R);
	} else {
		spray(k<<1,L,mid,l,mid);
		spray(k<<1|1,mid+1,R,mid+1,r);
		update(k,L,R);
	}
}
ll query(int k,int L,int R,int l,int r) {
	down(k,L,R);
	if (l==L&&r==R) {
		return get(seg[k]);
	} else {
		int mid=(L+R)>>1;
		if (r<=mid) {
			return query(k<<1,L,mid,l,r);
		} else if (l>mid) {
			return query(k<<1|1,mid+1,R,l,r);
		} else {
			return query(k<<1,L,mid,l,mid)+query(k<<1|1,mid+1,R,mid+1,r);
		}
	}
}
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d %d %d",&n,&q,&KK);
    int t;
    FOR(i,n) {
    	scanf("%d",&t);
    	change(1,1,n,i,t);
	}
	/*
	FOR(i,7) {
		queue<ll> q=seg[i];
		while (q.size()) {
			cout<<q.front()<<" ";
			q.pop();
		}
		cout<<endl;
	}*/
	
	int s,l,r;
	FOR(i,q) {
		scanf("%d %d %d",&s,&l,&r);
		if (s==1) {
			change(1,1,n,l,r);
		} else if (s==2) {
			if (KK==1) continue;
			spray(1,1,n,l,r); 
		} else {
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&q,&KK);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:130:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&t);
      ~~~~~^~~~~~~~~
sterilizing.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 269680 KB Output is correct
2 Correct 270 ms 269876 KB Output is correct
3 Correct 318 ms 269996 KB Output is correct
4 Correct 323 ms 270400 KB Output is correct
5 Correct 353 ms 270400 KB Output is correct
6 Correct 339 ms 270400 KB Output is correct
7 Correct 324 ms 270400 KB Output is correct
8 Correct 346 ms 270448 KB Output is correct
9 Correct 331 ms 270724 KB Output is correct
10 Correct 339 ms 270828 KB Output is correct
11 Correct 341 ms 270924 KB Output is correct
12 Correct 340 ms 270952 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 273692 KB Output is correct
2 Correct 748 ms 275124 KB Output is correct
3 Correct 922 ms 277392 KB Output is correct
4 Correct 1097 ms 279632 KB Output is correct
5 Correct 1225 ms 282340 KB Output is correct
6 Correct 1205 ms 284776 KB Output is correct
7 Correct 1186 ms 287108 KB Output is correct
8 Correct 1243 ms 289548 KB Output is correct
9 Correct 1164 ms 292128 KB Output is correct
10 Correct 1349 ms 294316 KB Output is correct
11 Correct 1195 ms 296736 KB Output is correct
12 Correct 1162 ms 298900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 298900 KB Output is correct
2 Correct 581 ms 298900 KB Output is correct
3 Correct 677 ms 298900 KB Output is correct
4 Correct 936 ms 299532 KB Output is correct
5 Correct 1493 ms 301692 KB Output is correct
6 Correct 1449 ms 303212 KB Output is correct
7 Correct 1230 ms 304828 KB Output is correct
8 Correct 1556 ms 306000 KB Output is correct
9 Correct 1420 ms 307236 KB Output is correct
10 Correct 1405 ms 308568 KB Output is correct
11 Correct 1372 ms 309820 KB Output is correct
12 Correct 1364 ms 311104 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1379 ms 312996 KB Output is correct
2 Correct 1325 ms 312996 KB Output is correct
3 Correct 1677 ms 325488 KB Output is correct
4 Correct 1399 ms 325488 KB Output is correct
5 Correct 2361 ms 325488 KB Output is correct
6 Correct 2301 ms 325488 KB Output is correct
7 Correct 1939 ms 325488 KB Output is correct
8 Correct 2528 ms 329440 KB Output is correct
9 Correct 2146 ms 332572 KB Output is correct
10 Correct 2411 ms 338572 KB Output is correct
11 Correct 2402 ms 344384 KB Output is correct
12 Correct 3281 ms 354524 KB Output is correct