Submission #70841

#TimeUsernameProblemLanguageResultExecution timeMemory
70841zadrgaSterilizing Spray (JOI15_sterilizing)C++14
0 / 100
1318 ms37796 KiB
// 15.22 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1LL << 55) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 100111 #define logn 35 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; ll K; ll arr[maxn]; struct segtree{ ll seg[4 * maxn][logn]; int lazy[4 * maxn]; void push(int x, int l, int d){ if(lazy[x] == 0) return; int k = lazy[x]; for(int i = 0; i + k < logn; i++) seg[x][i] = seg[x][i + k]; for(int i = logn - k; i < logn; i++) seg[x][i] = 0; if(l != d){ lazy[2 * x] += lazy[x]; lazy[2 * x + 1] += lazy[x]; } lazy[x] = 0; } void combine(int x, int l, int d){ for(int i = 0; i < logn; i++) seg[x][i] = seg[l][i] + seg[d][i]; } void setValue(int x, ll val){ seg[x][0] = val; for(int i = 1; i < logn; i++) seg[x][i] = seg[x][i - 1] / K; } void build(int x, int l, int d){ if(l > d) return; if(l == d){ setValue(x, arr[l]); lazy[x] = 0; return; } int mid = (l + d) / 2; build(2 * x, l, mid); build(2 * x + 1, mid + 1, d); combine(x, 2 * x, 2 * x + 1); lazy[x] = 0; } void update(int x, int l, int d, int i, ll val){ push(x, l, d); if(l > d || l > i || d < i) return; if(l == d && l == i){ setValue(x, val); return; } int mid = (l + d) / 2; update(2 * x, l, mid, i, val); update(2 * x + 1, mid + 1, d, i, val); combine(x, 2 * x, 2 * x + 1); } void reduce(int x, int l, int d, int i, int j){ push(x, l, d); if(l > d || l > j || d < i) return; if(i <= l && d <= j){ lazy[x] += 1; push(x, l, d); return; } int mid = (l + d) / 2; reduce(2 * x, l, mid, i, j); reduce(2 * x + 1, mid + 1, d, i, j); // combine(x, 2 * x, 2 * x + 1); } ll query(int x, int l, int d, int i, int j){ push(x, l, d); if(l > d || l > j || d < i) return 0; if(i <= l && d <= j) return seg[x][0]; int mid = (l + d) / 2; ll ret = query(2 * x, l, mid, i, j); ret += query(2 * x + 1, mid + 1, d, i, j); return ret; } }seg; int main(){ int n, q; scanf("%d%d%lld", &n, &q, &K); for(int i = 1; i <= n; i++) scanf("%lld", arr + i); seg.build(1, 1, n); while(q--){ ll t, x, y; scanf("%lld%lld%lld", &t, &x, &y); if(t == 1) seg.update(1, 1, n, x, y); if(t == 2) seg.reduce(1, 1, n, x, y); if(t == 3) printf("%lld\n", seg.query(1, 1, n, x, y)); } return 0; }

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &n, &q, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", arr + i);
   ~~~~~^~~~~~~~~~~~~~~~~
sterilizing.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &t, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...