Submission #534426

#	Time	Username	Problem	Language	Result	Execution time	Memory
534426		Haruto810198	Fire (JOI20_ho_t5)	C++17	100 / 100	272 ms	54692 KiB

ho_t5

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define double long double
 
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
 
#define vi vector<int>
#define pii pair<int, int>
 
#define F first
#define S second
 
#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define lsb(x) ((x)&(-(x)))

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 200010;

int n, q;
int arr[MAX];
int l[MAX], r[MAX];

int cnt[MAX], sum[MAX];

struct Query{
	int l, r, t, id;
};
Query query[MAX];
int res[MAX];

vi ev[MAX];
int owo;

void modify(int id, int val){
	
	owo += val; //
	int pos = id;

	//if(val == 1) cerr<<"+ ";
	//else cerr<<"- ";
	//cerr<<id<<endl;

	while(pos < n){
		cnt[pos] += val;
		sum[pos] += arr[id] * val;
		pos += lsb(pos);
	}
}

int search(int qcnt){
	int ret = 0;
	int ptr = 0;
	for(int j = 19; j >= 0; j--){
		int np = ptr + (1<<j);
		if(np >= n) continue;
		if(qcnt > cnt[np]){
			qcnt -= cnt[np];
			ret += sum[np];
			ptr = np;
		}
	}

	if(ptr + 1 <= n){
		ret += qcnt * arr[ptr + 1];
	}
	return ret;
}

signed main(){
	
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>q;
	FOR(i, 1, n, 1){
		cin>>arr[i];
	}

	FOR(i, 1, q, 1){
		cin>>query[i].t>>query[i].l>>query[i].r;
		query[i].id = i;
	}
	sort(query+1, query+q+1, [&](Query a, Query b){
		return (a.t < b.t);
	});
	
	arr[0] = arr[n+1] = INF;
	
	// l
	vi stk;
	stk.pb(0);
	FOR(i, 1, n, 1){
		while(arr[stk.back()] < arr[i]) stk.pop_back();
		l[i] = stk.back();
		stk.pb(i);
	}

	stk.clear();
	stk.pb(n+1);
	for(int i=n; i>=1; i--){
		while(arr[stk.back()] <= arr[i]) stk.pop_back();
		r[i] = stk.back();
		stk.pb(i);
	}
	
	// + : [1, r[i] - i - 1]
	// - : [i - l[i], i - l[i] + (r[i] - i - 1)]
	
	FOR(i, 1, n, 1){
		int ilen = r[i] - i - 1, dt = i - l[i];
		
		if(l[i] == 0){
			FOR(j, 1, ilen, 1){
				if(j > n) break;
				ev[j].pb(i);
			}
		}
		else{
			if(ilen < dt){
				FOR(j, 1, ilen, 1){
					if(j > n) break;
					ev[j].pb(i);
				}
				FOR(j, dt, dt + ilen, 1){
					if(j > n) break;
					ev[j].pb(-i);
				}
			}
			else{
				FOR(j, 1, dt - 1, 1){
					if(j > n) break;
					ev[j].pb(i);
				}
				FOR(j, ilen + 1, dt + ilen, 1){
					if(j > n) break;
					ev[j].pb(-i);
				}
			}
		}
	}
	
	// t = 0
	FOR(i, 1, n, 1){
		modify(i, 1);
	}
	
	int ptr = 0;
	FOR(i, 1, q, 1){
		while(ptr < query[i].t){
			// ptr -> ptr+1
			ptr++;
			for(int e : ev[ptr]){
				if(e > 0) modify(e, 1);
				else modify(-e, -1);
			}

			assert(owo == n);
		}
		
		res[query[i].id] = search(query[i].r) - search(query[i].l - 1);
		//cerr<<"query ["<<query[i].l<<", "<<query[i].r<<"] "<<endl;
	}
	
	FOR(i, 1, q, 1){
		cout<<res[i]<<'\n';
	}

	return 0;
	
}

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