제출 #447061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447061		maomao90	Fire (JOI20_ho_t5)	C++17	100 / 100	367 ms	44192 KiB

ho_t5

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 400025
#define BUF 200005

struct thing {
	int l, r, i;
};

int n, q;
int s[MAXN];
int l[MAXN], r[MAXN];
vector<thing> queries[MAXN], del[MAXN];
ll ans[MAXN];

struct fw {
	ll base[MAXN], mult[MAXN];
	void nincre(int i, ll x, ll* fw) {
		for (; i < MAXN; i += i & -i) fw[i] += x;
	}
	ll nqsum(int i, ll* fw) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += fw[i];
		return res;
	}
	void incre(int i, ll x) {
		nincre(i, (1 - i) * x, base);
		nincre(i, x, mult);
	}
	void incre(int s, int e, ll x) {
		s += BUF; e += BUF;
		incre(s, x);
		incre(e + 1, -x);
	}
	ll qsum(int i) {
		return nqsum(i, base) + nqsum(i, mult) * i;
	}
	ll qsum(int s, int e) {
		s += BUF; e += BUF;
		return qsum(e) - qsum(s - 1);
	}
} par, rect;

void tri(int l, int r, int x, bool todel = 0) {
	if (l > r) return;
	par.incre(l, n + 1, x);
	rect.incre(r + 1, n + 1, x);
	if (todel) {
		int len = r - l + 1;
		if (len <= n) del[len].pb({l, r, -x});
	}
}

int main() {
	scanf("%d%d", &n, &q);
	REP (i, 1, n + 1) {
		scanf("%d", &s[i]);
	}
	REP (i, 0, q) {
		int t, l, r; scanf("%d%d%d", &t, &l, &r);
		queries[t].pb({l, r, i});
	}
	vi stk;
	REP (i, 1, n + 1) {
		while (!stk.empty() && s[stk.back()] <= s[i]) {
			stk.pop_back();
		}
		if (!stk.empty()) {
			l[i] = stk.back();
		} else {
			l[i] = -n;
		}
		stk.pb(i);
	}
	stk.clear();
	RREP (i, n, 1) {
		while (!stk.empty() && s[stk.back()] < s[i]) {
			stk.pop_back();
		}
		if (!stk.empty()) {
			r[i] = stk.back();
		} else {
			r[i] = n + 1;
		}
		stk.pb(i);
	}
	REP (i, 1, n + 1) {
		tri(l[i] + 1, r[i] - 1, s[i], 1);
		tri(l[i] + 1, i - 1, -s[i], 1);
		tri(i + 1, r[i] - 1, -s[i], 1);
	}
	REP (t, 1, n + 1) {
		debug("%d\n", t);
#ifdef DEBUG
		REP (i, 1, n + 1) {
			debug(" %d", par.qsum(i - t, i - t) - rect.qsum(i, i));
		}
		debug("\n");
#endif
		for (thing& o : del[t]) {
			auto [l, r, v] = o;
			tri(l, r, v);
		}
		for (thing &o : queries[t]) {
			auto [l, r, i] = o;
			ans[i] = par.qsum(l - t, r - t) - rect.qsum(l, r);
		}
	}
	REP (i, 0, q) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d", &s[i]);
      |   ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:97:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   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