oj.uz

Submission #434715

# Submission time Handle Problem Language Result Execution time Memory
434715 2021-06-21T15:22:14 Z cpp219 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 2159 ms 5248 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 3 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 23 ms 348 KB Output is correct
5 Correct 25 ms 380 KB Output is correct
6 Correct 17 ms 388 KB Output is correct
7 Correct 26 ms 384 KB Output is correct
8 Correct 23 ms 392 KB Output is correct
9 Correct 30 ms 376 KB Output is correct
10 Correct 21 ms 332 KB Output is correct
11 Correct 21 ms 384 KB Output is correct
12 Correct 22 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1688 KB Output is correct
2 Correct 55 ms 1728 KB Output is correct
3 Correct 59 ms 2540 KB Output is correct
4 Correct 77 ms 2664 KB Output is correct
5 Correct 85 ms 2752 KB Output is correct
6 Correct 89 ms 2756 KB Output is correct
7 Correct 86 ms 2828 KB Output is correct
8 Correct 88 ms 2756 KB Output is correct
9 Correct 88 ms 2756 KB Output is correct
10 Correct 86 ms 2824 KB Output is correct
11 Correct 84 ms 2832 KB Output is correct
12 Correct 84 ms 2756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 472 KB Output is correct
2 Correct 38 ms 1260 KB Output is correct
3 Correct 45 ms 1432 KB Output is correct
4 Correct 88 ms 860 KB Output is correct
5 Correct 144 ms 2408 KB Output is correct
6 Correct 140 ms 2372 KB Output is correct
7 Correct 80 ms 2500 KB Output is correct
8 Correct 142 ms 2400 KB Output is correct
9 Correct 138 ms 2352 KB Output is correct
10 Correct 134 ms 2304 KB Output is correct
11 Correct 133 ms 2372 KB Output is correct
12 Correct 137 ms 2732 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 1516 KB Output is correct
2 Correct 472 ms 3308 KB Output is correct
3 Correct 988 ms 2592 KB Output is correct
4 Correct 594 ms 2816 KB Output is correct
5 Correct 846 ms 5180 KB Output is correct
6 Correct 1068 ms 5008 KB Output is correct
7 Correct 752 ms 5036 KB Output is correct
8 Correct 1455 ms 5248 KB Output is correct
9 Correct 1153 ms 5040 KB Output is correct
10 Correct 1429 ms 4976 KB Output is correct
11 Correct 878 ms 4936 KB Output is correct
12 Correct 2159 ms 5028 KB Output is correct