제출 #447061

#제출 시각아이디문제언어결과실행 시간메모리
447061maomao90Fire (JOI20_ho_t5)C++17
100 / 100
367 ms44192 KiB
#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);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...