Submission #95179

#TimeUsernameProblemLanguageResultExecution timeMemory
95179shashwatchandraSterilizing Spray (JOI15_sterilizing)C++17
80 / 100
5047 ms8044 KiB
/*input 15 10 3 25 87 32 89 24 99 57 88 10 57 65 42 66 98 13 3 9 12 1 7 15 3 2 9 2 1 14 3 10 13 1 10 6 2 14 14 1 7 96 3 14 15 3 10 12 */ #include<bits/stdc++.h> using namespace std; #define int long long #define double long double #define f first #define s second #define mp make_pair #define pb push_back #define RE(i,n) for (int i = 1; i <= n; i++) #define RED(i,n) for (int i = n; i > 0; i--) #define REPS(i,n) for(int i = 1; (i*i) <= n; i++) #define REP(i,n) for (int i = 0; i < n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define remax(a,b) a = max(a,b) #define remin(a,b) a = min(a,b) #define all(v) v.begin(),v.end() #define pii pair<int,int> #define mii map<int,int> #define vi vector<int> #define vvi vector<vi> #define WL(t) while(t --) #define gcd(a,b) __gcd((a),(b)) #define lcm(a,b) ((a)*(b))/gcd((a),(b)) #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl; #define debug(x) cout << x << endl; #define debug2(x,y) cout << x << " " << y << endl; #define debug3(x,y,z) cout << x << " " << y << " " << z << endl; const int INF = 1e18+1; const int MOD = 1e9+7; const double PI = 3.14159265358979323846264338; int fast_ex(int a,int n,int m){ if(n == 0)return 1; if(n == 1)return a; int x = 1; x *= fast_ex(a,n/2,m); x %= m; x *= x; x %= m; if(n%2)x*= a; x %= m; return x; } const int N = 1e5+1; pair<int,int> tree[4*N];//max,sum int a[N]; int n,q,k; void build(int node,int l,int r){ if(l == r){ tree[node] = {a[l],a[l]}; return; } int mid = (l+r)/2; build(2*node,l,mid); build(2*node+1,mid+1,r); tree[node].f = max(tree[node*2].f,tree[node*2 + 1].f); tree[node].s = tree[node*2].s+tree[node*2 + 1].s; } void range_update(int node,int l,int r,int start,int end){ //out of range if(l > end || r < start)return; if(!tree[node].f)return; if(l == r){ a[l] /= k; tree[node] = {a[l],a[l]}; return; } int mid = (l+r)/2; range_update(2*node,l,mid,start,end); range_update(2*node+1,mid+1,r,start,end); tree[node].f = max(tree[node*2].f,tree[node*2 + 1].f); tree[node].s = tree[node*2].s+tree[node*2 + 1].s; } void point_update(int node,int l,int r,int ind,int x){ if(l > ind || r < ind)return; if(l == r){ a[l] = x; tree[node] = {x,x}; return; } int mid = (l+r)/2; point_update(2*node,l,mid,ind,x); point_update(2*node+1,mid+1,r,ind,x); tree[node].f = max(tree[node*2].f,tree[node*2 + 1].f); tree[node].s = tree[node*2].s+tree[node*2 + 1].s; } int sum(int node,int l,int r,int start,int end){ if(l > end || r < start)return 0; if(l >= start && r <= end){ return tree[node].s; } int mid = (l+r)/2; return sum(2*node,l,mid,start,end)+sum(2*node+1,mid+1,r,start,end); } void solve(){ cin >> n >> q >> k; RE(i,n)cin >> a[i]; build(1,1,n); while(q--){ int type;cin >> type; if(type == 1){ int a,b;cin >> a >> b; point_update(1,1,n,a,b); } if(type == 2){ int l,r;cin >> l >> r; range_update(1,1,n,l,r); } if(type == 3){ int l,r;cin >> l >> r; cout << sum(1,1,n,l,r) << endl; } } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(".in","r",stdin);freopen(".out","w",stdout); int t = 1;//cin >> t; WL(t)solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...