제출 #992376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992376		PagodePaiva	Fish 3 (JOI24_fish3)	C++17	100 / 100	1241 ms	106672 KiB

Main

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N = 300010;
const int inf = 1e18;
const int debug = 0;

int n, q, d;
vector <pair <int, int>> intervalos;
int h[N];
vector <pair <int, int>> queries;
map <pair <int, int>, int> res;
set <int> s[N];

struct Segtree{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return min(a, b);
	}
	void unlazy(int node, int l, int r){
		tree[node] += lazy[node];
		if(l != r) {
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = h[l];
			lazy[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		lazy[node] = 0;
		return;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return inf;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} alturas;

struct Segtree2{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return a+b;
	}
	void unlazy(int node, int l, int r){
		tree[node] += lazy[node]*(r-l+1);
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = 0;
			lazy[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		lazy[node] = 0;
		return;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 0;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} resposta;

int32_t main(){
	cin >> n >> d;
	for(int i = 1;i <= n;i++)
		cin >> h[i];
	alturas.build(1, 1, n);
	cin >> q;
	for(int i = 0;i < q;i++){
		int a, b;
		cin >> a >> b;
		queries.push_back({a, b});
		s[b].insert(a);
	}
	res[{1, 1}] = 0;
	intervalos.push_back({1, 1});
	for(int r = 2;r <= n;r++){
		if(h[r] >= h[r-1]){
			if(h[r]-d < h[r-1]){
				auto [p, _] = intervalos.back();
				intervalos.pop_back();
				intervalos.push_back({p, r});
			}
			else intervalos.push_back({r, r});
		}
		else{
			auto [p, q] = intervalos.back();
			int res;
			int alt = h[r];
			if(debug and r == 3){
				cout << '(' << q << ' ' << alturas.query(1, q, q, 1, n) << ' ';
				cout << alt << ' ' << (alturas.query(1,q, q, 1, n) > alt) << ')';
			}
			while(alturas.query(1, q, q, 1, n) > alt){
				int t = (-(alt - alturas.query(1, q, q, 1, n))+d-1)/d;
				//cout << t << 'a';
				alturas.update(1, p, q, 1, n, -t*d);
				resposta.update(1, p, q, 1, n, t);
				alt = alturas.query(1, p, p, 1, n);
				intervalos.pop_back();
				res = p;
				if(intervalos.empty()) break;
				p = intervalos.back().first;
				q = intervalos.back().second;
			}
			intervalos.push_back({res, r});
		}
		if(debug){
			for(int i = 1;i <= r;i++)
				cout << resposta.query(1, i, r, 1, n) << ' ';
			cout << '\n';
		}
		for(auto l : s[r]){
			res[{l,r}] = (alturas.query(1, l, r, 1, n) < 0 ? -1 : resposta.query(1, l, r, 1, n));
		}
	}
	if(debug) cout << '\n' << '\n';
	for(auto x : queries){
		cout << res[x] << '\n';
	}
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36