Submission #236930

#	Time	Username	Problem	Language	Result	Execution time	Memory
236930		wwdd	Fire (JOI20_ho_t5)	C++14	100 / 100	617 ms	36364 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> ii;
typedef pair<int,ii> bro;
class LE {
	private:
		vi nx,pr,se;
		int n;
	public:
		LE() {
		}
		LE(int sz) {
			n = sz;
			nx.assign(n,0);
			pr.assign(n,0);
			se.assign(n,1);
			for(int i=0;i<n;i++) {
				if(i > 0) {
					pr[i] = i-1;
				}
				if(i < n-1) {
					nx[i] = i+1;
				}
			}
			nx[n-1] = pr[0] = -1;
		}
		int nex(int u) {
			return nx[u];
		}
		int pre(int u) {
			return pr[u];
		}
		int rem(int u) {
			//cout << "e " << u << '\n';
			int res = pr[u];
			//cout << pr[u] << " -> " << nx[u] << '\n';
			if(pr[u] != -1) {
				nx[pr[u]] = nx[u];
			}
			if(nx[u] != -1) {
				pr[nx[u]] = pr[u];
			}
			nx[u] = pr[u] = -1;
			se[u] = 0;
			return res;
		}
		int has(int u) {
			return se[u];
		}
};
class ST {
	private:
		vl st;
		int n,h;
	public:
		ST() {
		}
		ST(int sz) {
			n = 1;
			h = 1;
			while(n < sz) {n<<=1;h++;}
			st.assign(2*n,0);
		}
		void up(int p, ll val) {
			p += n;
			st[p] += val;
			while(p > 1) {
				st[p>>1] = st[p]+st[p^1];
				p >>= 1;
			}
		}
		ll get(int l, int r) {
			ll res = 0;
			for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
				if(l&1) {
					res += st[l];
					l++;
				}
				if(r&1) {
					--r;
					res += st[r];
				}
			}
			return res;
		}
		ll kth(ll num) {
			ll p = 1;
			for(int i=1;i<h;i++) {
				p <<= 1;
				if(st[p] < num) {
					num -= st[p];
					p++;
				}
			}
			return p-n;
		}
};
LE les,leg;
ST sa,sb;
vl w,fr;
vi act,mo;
vector<ii> so;
bool proc(ii& seg) {
	if(seg.second == seg.first) {return false;}
	int ra = seg.first, rb = seg.second;
	sa.up(ra,1);
	sb.up(ra,w[ra]);
	fr[ra]++;
	sa.up(rb,-1);
	sb.up(rb,-w[rb]);
	fr[rb]--;
	if(fr[rb] == 0) {
		seg.second = les.rem(rb);
	}
	return true;
}
void merge() {
	vi nu;
	for(int i=0;i<mo.size();i++) {
		if(!leg.has(mo[i])) {continue;}
		int id = mo[i];
		int re = so[id].second;
		int reg = leg.nex(id);
		while(reg != -1 && w[reg] <= w[re]) {
			leg.rem(reg);
			so[id].second = so[reg].second;
			reg = leg.nex(id);
			re = so[id].second;
		}
		if(so[id].second != so[id].first) {
			act.push_back(id);
		}
	}
	mo.clear();
}
void succ() {
	vi nu;
	for(int i=0;i<act.size();i++) {
		int u = act[i];
		if(!leg.has(u)) {continue;}
		proc(so[u]);
		int nt = leg.nex(u);
		if(w[so[u].second] >= w[nt]) {
			mo.push_back(u);
		} else if(so[u].first != so[u].second) {
			nu.push_back(u);
		}
	}
	act = nu;
}
ll ksu(int p) {
	if(p == 0) {return 0;}
	int num = sa.kth(p);
	ll res = sb.get(0,num);
	ll re = p-sa.get(0,num);
	res += w[num]*re;
	return res;
}
const int MN = 200200;
vector<bro> qv[MN];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin >> n >> q;
	les = LE(n);
	leg = LE(n);
	sa = ST(n);
	sb = ST(n);
	fr.assign(n,1);
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
		so.push_back({i,i});
		mo.push_back(i);
		sa.up(i,1);
		sb.up(i,w[i]);
	}
	for(int i=0;i<q;i++) {
		int a,b,c;
		cin >> a >> b >> c;
		b--;
		qv[a].push_back({i,{b,c}});
	}
	vl res(q,0);
	merge();
	for(int i=0;i<=n;i++) {
		/*
		for(int j=0;j<n;j++) {
			int u = sa.kth(j+1);
			cout << w[u] << " ";
		}
		cout << '\n';
		*/
		for(int j=0;j<qv[i].size();j++) {
			int idx = qv[i][j].first;
			ii co = qv[i][j].second;
			res[idx] = ksu(co.second)-ksu(co.first);
		}
		succ();
		merge();
	}
	for(int i=0;i<q;i++) {
		cout << res[i] << '\n';
	}
}

Compilation message (stderr)

ho_t5.cpp: In function 'void merge()':
ho_t5.cpp:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<mo.size();i++) {
              ~^~~~~~~~~~
ho_t5.cpp: In function 'void succ()':
ho_t5.cpp:141:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<act.size();i++) {
              ~^~~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:198:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<qv[i].size();j++) {
               ~^~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80