oj.uz

Submission #95181

# Submission time Handle Problem Language Result Execution time Memory
95181 2019-01-28T06:47:49 Z shashwatchandra Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 303 ms 8260 KB 
/*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;
           if(k > 1)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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 7 ms 504 KB Output is correct
9 Correct 7 ms 504 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 7 ms 760 KB Output is correct
12 Correct 7 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3168 KB Output is correct
2 Correct 85 ms 4728 KB Output is correct
3 Correct 70 ms 7004 KB Output is correct
4 Correct 90 ms 7860 KB Output is correct
5 Correct 119 ms 8116 KB Output is correct
6 Correct 119 ms 8176 KB Output is correct
7 Correct 119 ms 8184 KB Output is correct
8 Correct 119 ms 8260 KB Output is correct
9 Correct 107 ms 7968 KB Output is correct
10 Correct 104 ms 8056 KB Output is correct
11 Correct 104 ms 8056 KB Output is correct
12 Correct 104 ms 8056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 604 KB Output is correct
2 Correct 19 ms 2844 KB Output is correct
3 Correct 29 ms 2808 KB Output is correct
4 Correct 115 ms 1752 KB Output is correct
5 Correct 109 ms 5368 KB Output is correct
6 Correct 171 ms 5432 KB Output is correct
7 Correct 100 ms 5880 KB Output is correct
8 Correct 113 ms 6720 KB Output is correct
9 Correct 137 ms 6548 KB Output is correct
10 Correct 103 ms 6652 KB Output is correct
11 Correct 104 ms 6520 KB Output is correct
12 Correct 101 ms 6520 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 3148 KB Output is correct
2 Correct 131 ms 3192 KB Output is correct
3 Correct 146 ms 3308 KB Output is correct
4 Correct 171 ms 2180 KB Output is correct
5 Correct 197 ms 5724 KB Output is correct
6 Correct 207 ms 5880 KB Output is correct
7 Correct 181 ms 5876 KB Output is correct
8 Correct 246 ms 5752 KB Output is correct
9 Correct 218 ms 5836 KB Output is correct
10 Correct 236 ms 5880 KB Output is correct
11 Correct 189 ms 5828 KB Output is correct
12 Correct 303 ms 5840 KB Output is correct