oj.uz

Submission #942068

# Submission time Handle Problem Language Result Execution time Memory
942068 2024-03-10T07:47:39 Z dsyz Snowball (JOI21_ho_t2) C++17
0 / 100
 2500 ms 1248948 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
	ll s,e,m,v,lazy;
	node *l = nullptr, *r = nullptr;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		lazy = -1e18;
	}
	void create(){
		if(l == nullptr && s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo(){
		create();
		if(lazy == -1e18) return;
		v = (e-s+1) * lazy;
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = -1e18;
	}
	void update(ll x,ll y,ll nval){
		propo();
		if(s == x && e == y){
			lazy = nval;
		}else{
			create();
			if(x > m) r->update(x,y,nval);
			else if(y <= m) l->update(x,y,nval);
			else l->update(x,m,nval), r->update(m + 1,y,nval);
			l->propo(), r->propo();
			v = l->v + r->v;
		}
	}
	ll query(ll x,ll y){
		create();
		propo();
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r->query(x,y);
			else if(y <= m) return l->query(x,y);
			else return l->query(x,m) + r->query(m+1,y);
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	root = new node(0,2e13 + 10);
	root -> update(0,2e13 + 10,1);
	ll X[N];
	for(ll i = 0;i < N;i++){
		cin>>X[i];
		X[i] += (1e12 + 5);
	}
	ll ans[N];
	memset(ans,0,sizeof(ans));
	ll wind[Q];
	for(ll q = 0;q < Q;q++){
		cin>>wind[q];
		if(wind[q] > 0){ //blow right
			for(ll i = N - 1;i >= 0;i--){
				ans[i] += root -> query(X[i],X[i] + wind[q] - 1);
				root -> update(X[i],X[i] + wind[q] - 1,0);
				X[i] += wind[q];
			}
		}else if(wind[q] < 0){ //blow left
			wind[q] *= -1;
			for(ll i = 0;i < N;i++){
				ans[i] += root -> query(X[i] - wind[q],X[i] - 1);
				root -> update(X[i] - wind[q],X[i] - 1,0);
				X[i] -= wind[q];
			}
		}
	}
	for(ll i = 0;i < N;i++){
		cout<<ans[i]<<'\n';
	}
	cout<<'\n';
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40528 KB Output is correct
2 Correct 261 ms 232016 KB Output is correct
3 Execution timed out 2603 ms 1248948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40528 KB Output is correct
2 Correct 261 ms 232016 KB Output is correct
3 Execution timed out 2603 ms 1248948 KB Time limit exceeded
4 Halted 0 ms 0 KB -