oj.uz

Submission #95179

# Submission time Handle Problem Language Result Execution time Memory
95179 2019-01-28T06:45:00 Z shashwatchandra Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 8044 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;
           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 404 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 6 ms 396 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 6 ms 524 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 7 ms 508 KB Output is correct
9 Correct 7 ms 632 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 7 ms 504 KB Output is correct
12 Correct 7 ms 504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 4352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 760 KB Output is correct
2 Correct 22 ms 2936 KB Output is correct
3 Correct 32 ms 3192 KB Output is correct
4 Correct 96 ms 2808 KB Output is correct
5 Correct 118 ms 6748 KB Output is correct
6 Correct 116 ms 6904 KB Output is correct
7 Execution timed out 5006 ms 6320 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4088 KB Output is correct
2 Correct 135 ms 4728 KB Output is correct
3 Correct 145 ms 3976 KB Output is correct
4 Correct 171 ms 3636 KB Output is correct
5 Correct 195 ms 7928 KB Output is correct
6 Correct 215 ms 7928 KB Output is correct
7 Correct 188 ms 7936 KB Output is correct
8 Correct 259 ms 8044 KB Output is correct
9 Correct 221 ms 7928 KB Output is correct
10 Correct 243 ms 7880 KB Output is correct
11 Correct 191 ms 7928 KB Output is correct
12 Correct 311 ms 7832 KB Output is correct