oj.uz

Submission #434700

# Submission time Handle Problem Language Result Execution time Memory
434700 2021-06-21T15:08:18 Z cpp219 Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 5000 ms 2784 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));
                }
            }
        }
        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 5049 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 66 ms 2372 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 31 ms 388 KB Output is correct
2 Correct 38 ms 704 KB Output is correct
3 Correct 45 ms 824 KB Output is correct
4 Correct 102 ms 588 KB Output is correct
5 Correct 142 ms 1332 KB Output is correct
6 Correct 140 ms 1308 KB Output is correct
7 Correct 78 ms 2456 KB Output is correct
8 Correct 146 ms 2764 KB Output is correct
9 Correct 138 ms 2580 KB Output is correct
10 Correct 137 ms 2628 KB Output is correct
11 Correct 134 ms 2624 KB Output is correct
12 Correct 138 ms 2784 KB Output is correct

Subtask #4
0 / 75.0

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