Submission #202636

#	Time	Username	Problem	Language	Result	Execution time	Memory
202636		dndhk	Fire (JOI20_ho_t5)	C++14	100 / 100	279 ms	18668 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;

void solve1(){
	Seg.Init(N);
	for(int i=0; i<vt.size(); i++){
		ST now = vt[i];
		ll answer = 0;
		for(int j=now.l; j<=now.r; j++){
			answer += (ll)Seg.Mx(j-now.t, j);
		}
		printf("%lld\n", answer);
	}
}

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;
}

void solve2(){
	Seg.Init(N);
	int T = vt[0].t;
	for(int i=1; i<=N; i++){
		upd(i, (ll)Seg.Mx(i-T, i));
	}
	for(int i=0; i<vt.size(); i++){
		ST now = vt[i];
		printf("%lld\n", Sum(now.r) - Sum(now.l-1));
	}
}

void solve3(){
	Seg.Init(N);
	for(int i=0; i<vt.size(); i++){
		ST now = vt[i];
		printf("%lld\n", (ll)Seg.Mx(now.l-now.t, now.l));
	}
}

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]);
	}
	bool tf2 = true, tf3 = true;
	for(int i=1; i<=Q; i++){
		int t, l, r; scanf("%d%d%d", &t, &l, &r);
		vt.pb({t, l, r, i});
		if(t!=vt[0].t)	tf2 = false;
		if(l!=r)	tf3 = false;
	}
	if(N<=200 && Q<=200){
		solve1();
	}else if(tf2){
		solve2();
	}else if(tf3){
		solve3();
	}else{
		solve4();
	}
	return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void solve1()':
ho_t5.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
ho_t5.cpp: In function 'void solve2()':
ho_t5.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
ho_t5.cpp: In function 'void solve3()':
ho_t5.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
ho_t5.cpp: In function 'void solve4()':
ho_t5.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:149: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:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &S[i]);
   ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:155:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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