Submission #201028

#	Time	Username	Problem	Language	Result	Execution time	Memory
201028		gs14004	Fire (JOI20_ho_t5)	C++17	100 / 100	473 ms	47840 KiB

ho_t5

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 200005;
const int MAXT = 600050;

pi operator+(pi a, pi b){
	return pi(a.first + b.first, a.second + b.second);
}

struct bit{
	pi tree[MAXT];
	void add(int x, pi v){
		x += MAXN;
		for(int i=x; i<MAXT; i+=i&-i) tree[i] = tree[i] + v;
	}
	pi query(int x){
		x += MAXN;
		pi ret(0, 0);
		for(int i=x; i; i-=i&-i) ret = ret + tree[i];
		return ret;
	}
}bit1, bit2;

struct seg{
	pi tree[MAXT];
	int lim;
	void init(int n, int *a){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=1; i<=n; i++){
			tree[i + lim] = pi(a[i], i);
		}
		for(int i=lim; i; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
	}
	pi query(int s, int e){
		s += lim;
		e += lim;
		pi ret(-1e9, 1e9);
		while(s < e){
			if(s%2 == 1) ret = max(ret, tree[s++]);
			if(e%2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

struct ev1{ // y <= QUERY
	int upd, pos, val;
	bool operator<(const ev1 &e)const{
		return upd < e.upd;
	}
};

struct ev2{ // y - t <= QUERY
	int upd, pos, val;
	bool operator<(const ev2 &e)const{
		return upd < e.upd;
	}
};

vector<ev1> kek1;
vector<ev2> kek2;

void ADD(int x, int y, int v){
	int t = y - x;
	if(t > 1e7) return;
	kek1.push_back({t, y, v});
	kek2.push_back({t, x + 1, -v});
}

void solve(int s, int e){
	if(s > e) return;
	auto m = seg.query(s, e);
	solve(s, m.second - 1);
	solve(m.second + 1, e);
	if(s == 1) s = -1e9;
	int v = m.first;
	int p = m.second;
	ADD(p, p, v);
	ADD(p, e + 1, -v);
	ADD(s - 1, p, -v);
	ADD(s - 1, e + 1, v);
}

struct query{
	int t, r, idx, buho;
	bool operator<(const query &q)const{
		return t < q.t;
	}
}qr[MAXN * 2];

int n, q, a[MAXN];
lint ret[MAXN];

int main(){
	scanf("%d %d",&n,&q);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	seg.init(n, a);
	solve(1, n);
	for(int i=0; i<q; i++){
		int t, l, r;
		scanf("%d %d %d",&t,&l,&r);
		qr[2 * i] = {t, r, i, +1};
		qr[2 * i + 1] = {t, l-1, i, -1};
	}
	sort(qr, qr + q + q);
	sort(all(kek1));
	sort(all(kek2));
	int ptr1 = 0;
	int ptr2 = 0;
	for(int i=0; i<q*2; i++){
		while(ptr1 < sz(kek1) && kek1[ptr1].upd <= qr[i].t){
			bit1.add(kek1[ptr1].pos, pi(kek1[ptr1].val, 1ll * kek1[ptr1].val * (1 - kek1[ptr1].pos)));
			ptr1++;
		}
		while(ptr2 < sz(kek2) && kek2[ptr2].upd <= qr[i].t){
			bit2.add(kek2[ptr2].pos, pi(kek2[ptr2].val, 1ll * kek2[ptr2].val * (1 - kek2[ptr2].pos)));
			ptr2++;
		}
		lint sum = 0;
		auto qr1 = bit1.query(qr[i].r);
		sum += qr1.first * qr[i].r + qr1.second;
		auto qr2 = bit2.query(qr[i].r - qr[i].t);
		sum += qr2.first * (qr[i].r - qr[i].t) + qr2.second;
		ret[qr[i].idx] += qr[i].buho * sum;
	}
	for(int i=0; i<q; i++) printf("%lld\n", ret[i]);
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:103:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
                          ~~~~~^~~~~~~~~~~~
ho_t5.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&t,&l,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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