Submission #885752

#TimeUsernameProblemLanguageResultExecution timeMemory
885752qinFire (JOI20_ho_t5)C++17
14 / 100
257 ms54408 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define fi first #define se second #define pn printf("\n") #define ssize(x) int(x.size()) #define bitcount(x) __builtin_popcount(x) #define clz(x) __builtin_clz(x) #define ctz(x) __builtin_ctz(x) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef double db; typedef long double ldb; #define V vector /*void read(int &a){ char c = getchar_unlocked(); a = 0; while(c<'0' || '9'<c) c = getchar_unlocked(); while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked(); }*/ #ifdef DEBUG #define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n' #else #define debug(...) {} #endif int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1; int base = 1; struct seg{ struct Node{ ll a, b; int la, lb; Node(): a(0), b(0), la(0), lb(0) {} Node(ll aa, ll bb, int laa, int lbb) : a(aa), b(bb), la(laa), lb(lbb) {} }; vector<Node> t; vector<ll> tab; void merge(int &i){ t[i].a = t[i<<1].a + t[i<<1|1].a, t[i].b = t[i<<1].b + t[i<<1|1].b; t[i].la = t[i<<1].la + t[i<<1|1].la, t[i].lb = t[i<<1].lb + t[i<<1|1].lb; } void init(int n, vector<ll> &a){ while(base < n) base <<= 1; t.resize(base<<1); tab = a; for(int i = 1; i <= n; ++i) t[i+base-1] = Node(a[i], a[i], 1, 1); for(int i = base-1; i; --i) merge(i); } void update_point(int i, ll a, ll b, int la, int lb){ for(i += base-1, t[i] = Node(a, b, la, lb), i >>= 1; i; i >>= 1) merge(i); } ll first_k(int i, int s, int e, int &x, int &y, int &k, int &T){ if(!k) return 0; int mid = (s+e)>>1; if(x <= s && e <= y){ int sum = t[i].la*T + t[i].lb; if(sum <= k){ k -= sum; return t[i].a*T + t[i].b; } else{ if(s != e) return first_k(i<<1, s, mid, x, y, k, T) + first_k(i<<1|1, mid+1, e, x, y, k, T); else{ ll ret = tab[s]*k; k = 0; return ret; } } } ll ret = 0; if(x <= mid) ret += first_k(i<<1, s, mid, x, y, k, T); if(mid < y) ret += first_k(i<<1|1, mid+1, e, x, y, k, T); return ret; } ll query_interval(int i, int s, int e, int &x, int &y, int &T){ if(x <= s && e <= y){ //printf("%d %d\n", t[i].a, t[i].b); return t[i].a*T + t[i].b; } int mid = (s+e)>>1; ll ret = 0; if(x <= mid) ret += query_interval(i<<1, s, mid, x, y, T); if(mid < y) ret += query_interval(i<<1|1, mid+1, e, x, y, T); return ret; } ll query(int x, int y, int T){ if(x > y) return 0; return query_interval(1, 1, base, x, y, T); } ll firstk(int x, int y, int k, int T){ if(x > y) return 0; return first_k(1, 1, base, x, y, k, T); } }; struct ev{ int t, i; ev(){} ev(int tt, int ii) : t(tt), i(ii) {} bool operator <(const ev &x) const{ return t < x.t; } }; struct qr{ int a, b, i; qr(){} qr(int aa, int bb, int ii) : a(aa), b(bb), i(ii) {} }; void answer(){ int n, q; scanf("%d%d", &n, &q); vector<ll> t(n+1); vector<int> nxt(n+1), bef(n+1); for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]); seg seg; seg.init(n, t); vector<int> st; for(int i = 1; i <= n; ++i){ while(!st.empty() && t[st.back()] < t[i]) st.pop_back(); if(st.empty()) bef[i] = n+1; else bef[i] = i-st.back(); st.emplace_back(i); } st = vector<int>(); for(int i = n; i; --i){ while(!st.empty() && t[st.back()] < t[i]) st.pop_back(); if(st.empty()) nxt[i] = n+1-i; else nxt[i] = st.back()-i; st.emplace_back(i); } st = vector<int>(); vector<vector<ev>> event(n+2); set<int> active; for(int i = 1; i <= n; ++i) event[min(n+1, min(bef[i], nxt[i]))].emplace_back(0, i), event[min(n+1, max(bef[i], nxt[i]))].emplace_back(1, i), event[min(n+1, min(bef[i], nxt[i])+max(bef[i], nxt[i]))].emplace_back(2, i), active.emplace(i); //for(int i = 1; i <= n; ++i) printf("%d %d\n", bef[i], nxt[i]); vector<vector<qr>> queries(n+1); for(int i = 1; i <= q; ++i){ int a, b, T; scanf("%d%d%d", &T, &a, &b), queries[T].emplace_back(a, b, i);} vector<ll> result(q+1); for(int T = 1; T <= n; ++T){ for(ev &u : event[T]){ //printf("%d, %d: %d\n", T, u.i, u.t); if(!u.t){ if(u.i != 1) active.erase(u.i); //printf("%d %d\n", T, u.i); seg.update_point(u.i, 0, t[u.i]*T, 0, T); } else if(u.t == 1) seg.update_point(u.i, -t[u.i], t[u.i]*(min(bef[u.i], nxt[u.i])+T-1), -1, min(bef[u.i], nxt[u.i])+T-1); else seg.update_point(u.i, 0, 0, 0, 0); } for(qr &u : queries[T]){ auto it1 = active.upper_bound(u.a); it1 = prev(it1); auto it2 = active.upper_bound(u.b); it2 = prev(it2); result[u.i] = seg.query(*it1, (*it2)-1, T)-seg.firstk(*it1, u.a-1, u.a-(*it1), T)+seg.firstk(*it2, u.b, u.b-(*it2)+1, T); //printf("%d: %d %d: %lld %lld %lld\n", u.i, *it1, *it2, seg.query(*it1, (*it2)-1, T), seg.firstk(*it1, u.a-1, u.a-(*it1), T), seg.firstk(*it2, u.b, u.b-(*it2)+1, T)); //printf("%d %d %d, %lld\n", *it2, u.b, u.b-(*it2)+1, seg.firstk(*it2, u.b, u.b-(*it2)+1, T)); } //if(T == 3) printf("%lld\n", seg.query(4, 4, T)); } for(int i = 1; i <= q; ++i) printf("%lld\n", result[i]); } int main(){ int T = 1; //scanf("%d", &T); //ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; for(++T; --T; ) answer(); return 0; }

Compilation message (stderr)

ho_t5.cpp: In function 'void answer()':
ho_t5.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   int n, q; scanf("%d%d", &n, &q);
      |             ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:99:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~
ho_t5.cpp:122:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |   for(int i = 1; i <= q; ++i){ int a, b, T; scanf("%d%d%d", &T, &a, &b), queries[T].emplace_back(a, b, i);}
      |                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...