oj.uz

Submission #550288

# Submission time Handle Problem Language Result Execution time Memory
550288 2022-04-17T19:41:11 Z farhan132 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 989 ms 11836 KB 
/***Farhan132***/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast,fast-math")
 
 
#include <bits/stdc++.h>
 
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
 
const ll mod =  (ll) 998244353;
//const ll mod =  (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
const ll INF = (ll)1e18;
 
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};
 
bool USACO = 0;
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll N = 1e5 + 5;

struct fenwick{
  ll ft[N];
  void up(ll p, ll x) {
    for(; p < N; p += p & -p)
      ft[p] += x;
  } 
  ll sum(ll l, ll r) {
    ll ret = 0;
    for(--l; l > 0; l -= l & -l) ret -= ft[l];
    for(; r > 0; r -= r & -r) ret += ft[r];
    return ret;
  }
}T;
set < ll > s;
ll a[N];
vector < ll > nxt;
void change(ll i, ll v){
    T.up(i, -a[i] + v);
    a[i] = v;
    if(v) nxt.pb(i);
    return;
}

void solve(){

  ll n , k , q;
  cin >> n >> q >> k;
  mem(T.ft, 0);
  for(ll i = 1; i <= n; i++){
    ll x; cin >> x;
    change(i, x);
    s.in(i);
  }
  while(q--){
    ll t; cin >> t;
    if(t == 1){
        ll i, v;
        cin >> i >> v;
        if(a[i]) s.erase(i);
        change(i, v);
        if(v) s.in(i);
        continue;
    }
    ll l, r; cin >> l >> r;
    if(t == 2){
        if(k == 1) continue;
        nxt.clear(); 
        vector < ll > ultra;
        auto x = s.lower_bound(l);
        for(;x != s.end() && *x <= r; x++){
            ultra.pb(*x);
            change(*x, (a[*x] / k));
        }
        for(auto u : ultra) s.erase(u);
        for(auto u : nxt) s.in(u);
    }else{
        cout << T.sum(l, r) << '\n';
    }
  }
  
  
  return;
}
 
int main() {
    
    
    #ifdef LOCAL
        freopen("in", "r", stdin);
        freopen("out", "w", stdout);
        auto start_time = clock();
    #else 
       ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    #endif
 
    //pre(N);
 
    ll T = 1, CT = 0;  //cin >> T; 
 
    while(T--){
       //  cout << "Case #" << ++CT <<": " ;
        solve();
    }
    #ifdef LOCAL
        auto end_time = clock();
        cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n";
    #endif
 
    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:146:15: warning: unused variable 'CT' [-Wunused-variable]
  146 |     ll T = 1, CT = 0;  //cin >> T;
      |               ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 5 ms 1236 KB Output is correct
4 Correct 17 ms 1264 KB Output is correct
5 Correct 15 ms 1372 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 11 ms 1420 KB Output is correct
8 Correct 11 ms 1432 KB Output is correct
9 Correct 15 ms 1364 KB Output is correct
10 Correct 12 ms 1428 KB Output is correct
11 Correct 10 ms 1364 KB Output is correct
12 Correct 12 ms 1432 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4960 KB Output is correct
2 Correct 48 ms 3732 KB Output is correct
3 Correct 73 ms 6336 KB Output is correct
4 Correct 68 ms 7864 KB Output is correct
5 Correct 75 ms 8988 KB Output is correct
6 Correct 87 ms 8996 KB Output is correct
7 Correct 103 ms 9052 KB Output is correct
8 Correct 77 ms 9096 KB Output is correct
9 Correct 72 ms 9072 KB Output is correct
10 Correct 74 ms 8988 KB Output is correct
11 Correct 79 ms 9128 KB Output is correct
12 Correct 80 ms 9096 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1544 KB Output is correct
2 Correct 23 ms 4092 KB Output is correct
3 Correct 26 ms 4364 KB Output is correct
4 Correct 39 ms 3904 KB Output is correct
5 Correct 66 ms 8508 KB Output is correct
6 Correct 68 ms 8676 KB Output is correct
7 Correct 85 ms 9104 KB Output is correct
8 Correct 76 ms 8672 KB Output is correct
9 Correct 61 ms 8384 KB Output is correct
10 Correct 62 ms 8496 KB Output is correct
11 Correct 61 ms 8464 KB Output is correct
12 Correct 61 ms 8392 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 5064 KB Output is correct
2 Correct 177 ms 6600 KB Output is correct
3 Correct 384 ms 5776 KB Output is correct
4 Correct 232 ms 5216 KB Output is correct
5 Correct 331 ms 10912 KB Output is correct
6 Correct 434 ms 10716 KB Output is correct
7 Correct 331 ms 11068 KB Output is correct
8 Correct 608 ms 11012 KB Output is correct
9 Correct 542 ms 11416 KB Output is correct
10 Correct 664 ms 11700 KB Output is correct
11 Correct 373 ms 11568 KB Output is correct
12 Correct 989 ms 11836 KB Output is correct