oj.uz

Submission #434714

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

#include <bits/stdc++.h>
#define ll long long
#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,a[N];

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 10 ms 332 KB Output is correct
4 Correct 70 ms 332 KB Output is correct
5 Correct 179 ms 440 KB Output is correct
6 Correct 186 ms 332 KB Output is correct
7 Correct 181 ms 440 KB Output is correct
8 Correct 177 ms 452 KB Output is correct
9 Correct 186 ms 444 KB Output is correct
10 Correct 186 ms 452 KB Output is correct
11 Correct 177 ms 436 KB Output is correct
12 Correct 190 ms 436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1696 KB Output is correct
2 Correct 69 ms 3316 KB Output is correct
3 Correct 63 ms 4304 KB Output is correct
4 Correct 78 ms 4840 KB Output is correct
5 Correct 92 ms 5256 KB Output is correct
6 Correct 88 ms 5224 KB Output is correct
7 Correct 89 ms 5176 KB Output is correct
8 Correct 90 ms 5352 KB Output is correct
9 Correct 85 ms 5048 KB Output is correct
10 Correct 85 ms 5096 KB Output is correct
11 Correct 85 ms 5080 KB Output is correct
12 Correct 85 ms 5084 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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