Submission #879010

#TimeUsernameProblemLanguageResultExecution timeMemory
879010hafoSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
949 ms8020 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e18 + 69; int n, q, k, t, l, r, a[maxn]; struct ST { struct node { ll sum; int mx, pos; friend node operator + (node a, const node &b) { if(a.mx == 0) a.mx = b.mx, a.pos = b.pos; a.sum += b.sum; return a; } }; node st[4 * maxn]; void build(int id, int l, int r) { if(l == r) { st[id] = {a[l], a[l], l}; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void update(int id, int l, int r, int pos, int val) { if(pos < l || pos > r) return; if(l == r) { st[id] = {val, val, l}; return; } int mid = l + r >> 1; update(id << 1, l, mid, pos, val); update(id << 1 | 1, mid + 1, r, pos, val); st[id] = st[id << 1] + st[id << 1 | 1]; } node get(int id, int l, int r, int u, int v) { if(r < u || l > v) return {0, 0, n + 1}; if(u <= l && r <= v) return st[id]; int mid = l + r >> 1; return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v); } } st; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>q>>k; for(int i = 1; i <= n; i++) cin>>a[i]; st.build(1, 1, n); while(q--) { cin>>t>>l>>r; if(t == 1) { st.update(1, 1, n, l, r); } if(t == 2) { while(k > 1) { if(l > r) break; auto tmp = st.get(1, 1, n, l, r); if(tmp.mx == 0) break; st.update(1, 1, n, tmp.pos, tmp.mx / k); l = tmp.pos + 1; } } if(t == 3) { cout<<st.get(1, 1, n, l, r).sum<<"\n"; } } return 0; }

Compilation message (stderr)

sterilizing.cpp: In member function 'void ST::build(int, int, int)':
sterilizing.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'void ST::update(int, int, int, int, int)':
sterilizing.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         int mid = l + r >> 1;
      |                   ~~^~~
sterilizing.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
sterilizing.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 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...