Submission #879855

#TimeUsernameProblemLanguageResultExecution timeMemory
879855efedmrlrFire (JOI20_ho_t5)C++17
0 / 100
650 ms77776 KiB
#include <bits/stdc++.h> using namespace std; #define n_l '\n' #define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)), __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } #define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl #define int long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++) void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const double EPS = 0.00001; const int INF = 1e16; const int N = 2e5+5; const int ALPH = 26; const int LGN = 20; const int MOD = 1e9+7; int n,m,q; int lastBIT(int x) { return x & (-x); } struct BITree { vector<int> data; int sz; BITree(int sz) { data.assign(sz + 5, 0); this->sz = sz; } void update(int ind, int val) { ind++; while(ind <= sz) { data[ind] += val; ind = ind + lastBIT(ind); } } int query(int ind) { ind++; int ret = 0ll; while(ind > 0ll) { ret += data[ind]; ind = ind - lastBIT(ind); } return ret; } int query(int l, int r) { return query(r) - query(l - 1ll); } void set_el(int ind, int val) { update(ind, val - query(ind, ind)); } }; struct Event { int t, el, type; Event() { t = 0; el = 0; type = 0; } Event(int tm, int e, int ty) { t = tm; el = e; type = ty; } const bool operator<(const Event &oth) { return t < oth.t; } void print() { cout<<"time: "<<t<<" el:"<<el<<" type: "<<type; cout<<"\n"; } }; struct Query { int t, l,r, ind; Query() { t = 0; l = 0; r = 0; ind = 0; } Query(int tm, int lf, int rg, int id) { t = tm; l = lf; r = rg; ind = id; } const bool operator<(const Query &oth) { return t < oth.t; } void input(int id) { cin>>t>>l>>r; ind = id; } void print() { dbg(t); dbg(l); dbg(r); dbg(ind); } }; vector<Event> evs; /* type 1 = expansion to stable type 2 = stable to decay type 3 = decay to death times are the start time of coming phase */ vector<Query> que; vector<int> s; vector<int> lg, rg; void getEvents() { evs.clear(); for(int i = 1; i<=n; i++) { int ev1 = min(rg[i] - i, i - lg[i]), ev2 = max(rg[i] - i, i - lg[i]); int ev3 = rg[i] - lg[i]; evs.pb(Event(ev1, i, 1)); evs.pb(Event(ev2, i, 2)); evs.pb(Event(ev3, i, 3)); } sort(evs.rbegin(), evs.rend()); } void find_greater() { set<int> st; vector<array<int,2> > sc(n); for(int i = 1; i<=n; i++) { sc[i - 1] = {s[i], i}; } sort(sc.rbegin(), sc.rend()); st.insert(0); st.insert(n + 1); for(auto c : sc) { rg[c[1]] = *st.upper_bound(c[1]); st.insert(c[1]); } st.clear(); st.insert(-INF); st.insert(n + 1); for(auto c : sc) { lg[c[1]] = *prev(st.upper_bound(c[1])); st.insert(c[1]); } } vector<int> anc[LGN]; void calc_anc() { for(int i = 0; i<LGN; i++) { anc[i].assign(n+3, 0); } for(int i = 1; i<=n; i++) { if(lg[i] == -INF) anc[0][i] = 0ll; else anc[0][i] = lg[i]; } for(int k = 1; k<LGN; k++) { for(int i = 1; i<=n; i++) { anc[k][i] = anc[k - 1][anc[k - 1][i]]; } } } int find_anc(int node, int cap) { for(int i = LGN - 1; i>=0; i--) { if(anc[i][node] != 0 && anc[i][node] >= cap) { node = anc[i][node]; } } return node; } int calcRBound(int tm, int r, BITree &expand, BITree &stable, BITree &decay, BITree &decay_t) { int edge = find_anc(r, r - tm); // dbg(tm); dbg(r); // dbg(edge); int ret = 0; if(edge > 1) { ret += expand.query(edge - 1ll) * (tm + 1ll); ret += stable.query(edge - 1ll); ret += decay.query(edge - 1ll); ret += decay_t.query(edge - 1ll) * tm; } int edger = r; int edgel = edge; if(anc[0][edgel] != 0ll) { edgel = anc[0][edgel] + tm + 1ll; } // dbg(ret); ret += s[edge] * max(0ll, edger - edgel + 1ll); // dbg(s[edge] * max(0ll, edger - edgel + 1)); return ret; } int calcQuery(Query cur, BITree &expand, BITree &stable, BITree &decay, BITree &decay_t) { return calcRBound(cur.t, cur.r, expand, stable, decay, decay_t) - (cur.l < 2 ? 0ll : calcRBound(cur.t, cur.l - 1, expand, stable, decay, decay_t)); } inline void solve() { cin>>n>>q; s.assign(n+3, 0); lg.assign(n+3, 0); rg.assign(n+3, 0); que.assign(q, Query()); REP(i,n) cin>>s[i + 1]; REP(i,q) que[i].input(i + 1); sort(que.begin(), que.end()); find_greater(); getEvents(); calc_anc(); // dbg(lg); dbg(rg); BITree expand(n + 3), stable(n + 3), decay(n + 3), decay_t(n + 3); vector<int> res(q+3, 0); for(int i = 1; i<=n; i++) { expand.set_el(i, s[i]); } // for(int i = 0; i<evs.size(); i++) evs[i].print(); for(auto cur : que) { //adjust Events // cur.print(); while(evs.size() && cur.t >= evs.back().t) { auto ev = evs.back(); evs.pop_back(); if(ev.type == 1) { expand.set_el(ev.el, 0); stable.set_el(ev.el, ev.t * s[ev.el]); } else if(ev.type == 2) { decay.set_el(ev.el, (ev.t - 1) * s[ev.el]) ; decay_t.set_el(ev.el, -1ll * s[ev.el]); } else if(ev.type == 3) { stable.set_el(ev.el, 0); decay.set_el(ev.el, 0); decay_t.set_el(ev.el, 0); } else { // ev.print(); assert(0); } } // cout<<"events done"<<endl; res[cur.ind] = calcQuery(cur, expand, stable, decay, decay_t); } for(int i = 1; i<=q; i++) { cout<<res[i]<<"\n"; } } signed main() { //fastio(); int test = 1; //cin>>test; while(test--) { solve(); } }

Compilation message (stderr)

ho_t5.cpp: In function 'std::string to_string(std::string, int, int)':
ho_t5.cpp:7:208: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); }
      |                                                                                                                                                                                                             ~~~^~~~~~~~~~
ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:14:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
      |                          ^
ho_t5.cpp:203:5: note: in expansion of macro 'REP'
  203 |     REP(i,n) cin>>s[i + 1];
      |     ^~~
ho_t5.cpp:14:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
      |                          ^
ho_t5.cpp:204:5: note: in expansion of macro 'REP'
  204 |     REP(i,q) que[i].input(i + 1);
      |     ^~~
#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...