oj.uz

Submission #57408

# Submission time Handle Problem Language Result Execution time Memory
57408 2018-07-15T00:11:29 Z Benq Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 333 ms 72580 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<class T, int SZ> struct BIT {
    T bit[SZ+1];
    
    BIT() { memset(bit,0,sizeof bit); }
    
    void upd(int k, T val) { // add val to index k
        for( ;k <= SZ; k += (k&-k)) bit[k] += val;
    }
    
    T query(int k) {
        T temp = 0;
        for (;k > 0;k -= (k&-k)) temp += bit[k];
        return temp;
    }
    T query(int l, int r) { return query(r)-query(l-1); } // range query [l,r]
};

BIT<ll,MX> B;
int N,Q,K,A[MX];
map<int,int> x;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> Q >> K;
    FOR(i,1,N+1) {
        cin >> A[i];
        if (A[i]) {
            B.upd(i,A[i]);
            x[i] = A[i];
        }
    }
    F0R(i,Q) {
        int S,T,U; cin >> S >> T >> U;
        if (S == 1) {
            if (A[T]) {
                B.upd(T,-A[T]);
                x.erase(T);
            }
            A[T] = U;
            if (A[T]) {
                B.upd(T,A[T]);
                x[T] = A[T];
            }
        } else if (S == 2) {
            if (K == 1) continue;
            auto it = x.lb(T);
            while (it != x.end() && it->f <= U) {
                B.upd(it->f,-it->s);
                it->s /= K; 
                A[it->f] = it->s;
                B.upd(it->f,it->s);
                it = next(it);
                if (prev(it)->s == 0) x.erase(prev(it));
            }
        } else {
            cout << B.query(T,U) << "\n";
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1300 KB Output is correct
3 Correct 5 ms 1448 KB Output is correct
4 Correct 10 ms 1488 KB Output is correct
5 Correct 11 ms 1832 KB Output is correct
6 Correct 10 ms 1880 KB Output is correct
7 Correct 10 ms 1948 KB Output is correct
8 Correct 13 ms 2004 KB Output is correct
9 Correct 14 ms 2060 KB Output is correct
10 Correct 9 ms 2120 KB Output is correct
11 Correct 10 ms 2308 KB Output is correct
12 Correct 12 ms 2504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7240 KB Output is correct
2 Correct 79 ms 8068 KB Output is correct
3 Correct 85 ms 11744 KB Output is correct
4 Correct 118 ms 15120 KB Output is correct
5 Correct 163 ms 17616 KB Output is correct
6 Correct 125 ms 20068 KB Output is correct
7 Correct 165 ms 22484 KB Output is correct
8 Correct 143 ms 25156 KB Output is correct
9 Correct 141 ms 27324 KB Output is correct
10 Correct 143 ms 29664 KB Output is correct
11 Correct 119 ms 31940 KB Output is correct
12 Correct 113 ms 34348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34348 KB Output is correct
2 Correct 24 ms 34348 KB Output is correct
3 Correct 28 ms 34348 KB Output is correct
4 Correct 71 ms 34348 KB Output is correct
5 Correct 83 ms 35564 KB Output is correct
6 Correct 86 ms 36860 KB Output is correct
7 Correct 99 ms 38412 KB Output is correct
8 Correct 82 ms 39696 KB Output is correct
9 Correct 98 ms 41020 KB Output is correct
10 Correct 75 ms 42248 KB Output is correct
11 Correct 82 ms 43636 KB Output is correct
12 Correct 76 ms 44800 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 46364 KB Output is correct
2 Correct 138 ms 48216 KB Output is correct
3 Correct 153 ms 48928 KB Output is correct
4 Correct 187 ms 50016 KB Output is correct
5 Correct 214 ms 55900 KB Output is correct
6 Correct 199 ms 58480 KB Output is correct
7 Correct 199 ms 60820 KB Output is correct
8 Correct 333 ms 63276 KB Output is correct
9 Correct 249 ms 65728 KB Output is correct
10 Correct 321 ms 68020 KB Output is correct
11 Correct 235 ms 70216 KB Output is correct
12 Correct 311 ms 72580 KB Output is correct