Submission #480108

#	Time	Username	Problem	Language	Result	Execution time	Memory
480108		HynDuf	Fire (JOI20_ho_t5)	C++11	100 / 100	241 ms	21532 KiB

ho_t5

#include <bits/stdc++.h>
 
#define pb push_back
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
 
const int MAX_N = 200000;
 
int N, Q;
int S[MAX_N+1];
 
struct ST{
	int t, l, r, idx;
	bool operator <(const ST &a)const{
		return t<a.t;
	}
};
 
vector<ST> vt;
 
 
struct SEG{
	struct NODE{
		int l, r;
		int mx;
	};
	vector<NODE> seg;
	int SZ;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add(); init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	{
			seg[idx].mx = S[s];
			return;
		}
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
		seg[idx].mx = max(seg[seg[idx].l].mx, seg[seg[idx].r].mx);
	}
	int  Mx(int x, int y){
		return mx(0, 1, SZ, x, y);
	}
	int mx(int idx, int s, int e, int x, int y){
		if(x>e || y<s)	return 0;
		if(x<=s && e<=y)	return seg[idx].mx;
		return max(mx(seg[idx].l, s, (s+e)/2, x, y), mx(seg[idx].r, (s+e)/2+1, e, x, y));
	}
}Seg;
 
ll tree[MAX_N+1];
 
void upd(int x, ll y){
	while(x<=N){
		tree[x]+=y;
		x+=(x&-x);
	}
}
 
ll Sum(int x){
	ll ret = 0;
	while(x>0){
		ret+=tree[x];
		x-=(x&-x);
	}
	return ret;
}

 
ll ans[MAX_N+1];
 
vector<pii> v, v2;
 
void solve4(){
	Seg.Init(N);
	sort(vt.begin(), vt.end());
	int T = 0;
	for(int i=1; i<=N; i++){
		upd(i, S[i]);
		if(S[i]!=0){
			v.pb({i, S[i]});
		}
	}
	for(int i=0; i<vt.size(); i++){
		ST now = vt[i];
		while(T<now.t){
			T++;
			while(!v.empty()){
				pii n = v.back(); v.pop_back();
				if(n.first==N)	continue;
				if(S[n.first+1]<n.second){
					upd(n.first+1, (ll)(n.second-S[n.first+1]));
					S[n.first+1] = n.second;
					v2.pb({n.first+1, n.second});
				}
			}
			while(!v2.empty()){
				v.pb(v2.back()); v2.pop_back();
			}
		}
		ans[now.idx] = Sum(now.r) - Sum(now.l-1);
	}
	for(int i=1; i<=Q; i++){
		printf("%lld\n", ans[i]);
	}
}
int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++){
		scanf("%d", &S[i]);
	}
	for(int i=1; i<=Q; i++){
		int t, l, r; scanf("%d%d%d", &t, &l, &r);
		vt.pb({t, l, r, i});
	}
	solve4();
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void solve4()':
ho_t5.cpp:94:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i=0; i<vt.size(); i++){
      |               ~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |   scanf("%d", &S[i]);
      |   ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:123:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |   int t, l, r; 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