oj.uz

Submission #434703

# Submission time Handle Problem Language Result Execution time Memory
434703 2021-06-21T15:11:41 Z cpp219 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 5000 ms 1476 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e5 + 9;
const ll mod = 1e9 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;

ll n,Q,k,x;

ll st[4*N];

void upd(ll id,ll l,ll r,ll u,ll val){
    if (u < l||r < u) return;
    if (l == r){
        st[id] = val; return;
    }
    ll mid = (l + r)/2;
    upd(id*2,l,mid,u,val); upd(id*2 + 1,mid + 1,r,u,val);
    st[id] = st[id*2] + st[id*2 + 1];
}

ll Get(ll id,ll l,ll r,ll u,ll v){
    if (v < l||r < u) return 0;
    if (u <= l&&r <= v) return st[id];
    ll mid = (l + r)/2;
    return Get(id*2,l,mid,u,v) + Get(id*2 + 1,mid + 1,r,u,v);
}

ll Walk(ll id,ll l,ll r,ll val){
    ///first value which > val
    if (l == r){
        if (st[id] > val) return l;
        return n + 1;
    }
    ll mid = (l + r)/2;
    if (st[id*2] > val) return Walk(id*2,l,mid,val);
    return Walk(id*2 + 1,mid + 1,r,val - st[id*2]);
}

ll type,l,r;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>Q>>k;
    for (ll i = 1;i <= n;i++) cin>>x,upd(1,1,n,i,x);
    while(Q--){
        cin>>type>>l>>r;
        if (type == 1) upd(1,1,n,l,r);
        else if (type == 2){
            if (k > 1){
                while(l <= r){
                    ll now = Get(1,1,n,l,l); now /= k;
                    upd(1,1,n,l,now); l = Walk(1,1,n,Get(1,1,n,1,l));
                    //l++;
                }
            }
        }
        else cout<<Get(1,1,n,l,r)<<"\n";
    }
}

Compilation message

sterilizing.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
sterilizing.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 1092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 388 KB Output is correct
2 Correct 37 ms 792 KB Output is correct
3 Correct 45 ms 824 KB Output is correct
4 Correct 85 ms 608 KB Output is correct
5 Correct 144 ms 1448 KB Output is correct
6 Correct 142 ms 1352 KB Output is correct
7 Correct 79 ms 1476 KB Output is correct
8 Correct 140 ms 1372 KB Output is correct
9 Correct 134 ms 1356 KB Output is correct
10 Correct 135 ms 1332 KB Output is correct
11 Correct 135 ms 1284 KB Output is correct
12 Correct 139 ms 1348 KB Output is correct

Subtask #4
0 / 75.0

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