Submission #784570

#TimeUsernameProblemLanguageResultExecution timeMemory
784570AcanikolicSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
113 ms7740 KiB
#include <bits/stdc++.h> #define ll long long #define int long long #define pb push_back #define F first #define S second using namespace std; const long long N = 1e5+10; const long long mod = 1e9+7; const long long inf = 1e18; vector<int>ft(N); void update(int index,int n,int val) { while(index <= n) { ft[index] += val; index += index & -index; } } int get(int x) { int X = 0; while(x >= 1) { X += ft[x]; x -= x & -x; } return X; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,Q,k; cin >> n >> Q >> k; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin >> a[i]; update(i,n,a[i]); } if(k == 1) { while(Q--) { int type; cin >> type; if(type == 1) { int index,val; cin >> index >> val; update(index,n,val-a[index]); a[index] = val; } else if(type == 2) { int l,r; cin >> l >> r; } else { int l,r; cin >> l >> r; cout << get(r)-get(l-1) << '\n'; } } return 0; } set<int>st; for(int i=1;i<=n;i++) { if(a[i] >= 1) st.insert(i); } while(Q--) { int type; cin >> type; if(type == 1) { int index,val; cin >> index >> val; update(index,n,val-a[index]); a[index] = val; if(st.find(index) == st.end() && val >= 1) st.insert(index); } else if(type == 2) { int l,r; cin >> l >> r; auto lb = st.lower_bound(l); vector<int>X; //cout << "menjam : "; for(lb;lb!=st.end()&&*lb<=r;lb++) { int x = a[*lb]/k; update(*lb,n,x-a[*lb]); //cout << *lb << ' ' << get(*lb)-get(*lb-1) << endl; a[*lb] = x; if(a[*lb] == 0) X.pb(*lb); } //cout << endl; for(int i=0;i<X.size();i++) st.erase(X[i]); //for(int i=1;i<=n;i++) cout << get(i) << ' '; //cout << endl; } else { int l,r; cin >> l >> r; cout << get(r)-get(l-1) << '\n'; } } return 0; }

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:93:8: warning: statement has no effect [-Wunused-value]
   93 |    for(lb;lb!=st.end()&&*lb<=r;lb++) {
      |        ^~
sterilizing.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    for(int i=0;i<X.size();i++) st.erase(X[i]);
      |                ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...