oj.uz

Submission #972797

# Submission time Handle Problem Language Result Execution time Memory
972797 2024-05-01T07:57:45 Z yeediot Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 133 ms 10408 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
int n,q,k;
const int mxn=1e5+5;
int a[mxn];
struct state{
    int mx,sum;
};
struct segtree{
    state seg[4*mxn];
    void pull(int id,int l,int r){
        seg[id].mx=max(seg[l].mx,seg[r].mx);
        seg[id].sum=seg[l].sum+seg[r].sum;
    }
    void build(int l,int r,int id){
        if(l==r){
            seg[id].sum=seg[id].mx=a[l];
            return ;
        }
        int mm=l+r>>1;
        build(l,mm,id*2);
        build(mm+1,r,id*2+1);
        pull(id,id*2,id*2+1);
    }
    void modify(int l,int r,int id,int p,int v){
        if(l==r){
            seg[id].mx=seg[id].sum=v;
            return;
        }
        int mm=l+r>>1;
        if(p<=mm){
            modify(l,mm,id*2,p,v);
        }
        else{
            modify(mm+1,r,id*2+1,p,v);
        }
        pull(id,id*2,id*2+1);
    }
    void modify(int p,int v){
        modify(1,n,1,p,v);
    }
    void go(int l,int r,int id,int ql,int qr){
        if(r<ql or qr<l){
            return;
        }
        if(l==r){
            seg[id].mx/=k;
            seg[id].sum/=k;
            return ;
        }
        int mm=l+r>>1;
        if(seg[id*2].mx>0){
            go(l,mm,id*2,ql,qr);
        }
        if(seg[id*2+1].mx>0){
            go(mm+1,r,id*2+1,ql,qr);
        }
        pull(id,id*2,id*2+1);
    }
    void go(int ql,int qr){
        go(1,n,1,ql,qr);
    }
    int query(int l,int r,int id,int ql,int qr){
        if(qr<l or r<ql){
            return 0;
        }
        if(ql<=l and r<=qr){
            return seg[id].sum;
        }
        int mm=l+r>>1;
        return query(l,mm,id*2,ql,qr)+query(mm+1,r,id*2+1,ql,qr);
    }
    int query(int ql,int qr){
        return query(1,n,1,ql,qr);
    }
}tr;
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    tr.build(1,n,1);
    for(int i=1;i<=q;i++){
        int ty,x,y;
        cin>>ty>>x>>y;
        if(ty==1){
            tr.modify(x,y);
        }   
        else if(ty==2 and k!=1){
            tr.go(x,y);
        }
        else if(ty==3){
            cout<<tr.query(x,y)<<'\n';
        }
    }
}
 /*
 input:
 
 */

Compilation message

sterilizing.cpp: In member function 'void segtree::build(long long int, long long int, long long int)':
sterilizing.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mm=l+r>>1;
      |                ~^~
sterilizing.cpp: In member function 'void segtree::modify(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mm=l+r>>1;
      |                ~^~
sterilizing.cpp: In member function 'void segtree::go(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:102:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int mm=l+r>>1;
      |                ~^~
sterilizing.cpp: In member function 'long long int segtree::query(long long int, long long int, long long int, long long int, long long int)':
sterilizing.cpp:121:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |         int mm=l+r>>1;
      |                ~^~
sterilizing.cpp: In function 'void setIO(std::string)':
sterilizing.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 3 ms 2424 KB Output is correct
6 Correct 3 ms 2652 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 3 ms 2904 KB Output is correct
9 Correct 3 ms 2652 KB Output is correct
10 Correct 3 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5460 KB Output is correct
2 Correct 32 ms 6740 KB Output is correct
3 Correct 27 ms 9044 KB Output is correct
4 Correct 38 ms 9812 KB Output is correct
5 Correct 43 ms 10408 KB Output is correct
6 Correct 42 ms 10392 KB Output is correct
7 Correct 42 ms 10356 KB Output is correct
8 Correct 43 ms 10332 KB Output is correct
9 Correct 40 ms 10064 KB Output is correct
10 Correct 39 ms 10072 KB Output is correct
11 Correct 39 ms 10064 KB Output is correct
12 Correct 40 ms 10268 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4700 KB Output is correct
2 Correct 8 ms 4956 KB Output is correct
3 Correct 11 ms 4956 KB Output is correct
4 Correct 33 ms 4952 KB Output is correct
5 Correct 40 ms 7512 KB Output is correct
6 Correct 39 ms 7512 KB Output is correct
7 Correct 35 ms 7516 KB Output is correct
8 Correct 42 ms 8808 KB Output is correct
9 Correct 36 ms 8792 KB Output is correct
10 Correct 37 ms 8844 KB Output is correct
11 Correct 36 ms 8784 KB Output is correct
12 Correct 47 ms 8656 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5200 KB Output is correct
2 Correct 53 ms 5200 KB Output is correct
3 Correct 62 ms 5364 KB Output is correct
4 Correct 65 ms 4952 KB Output is correct
5 Correct 76 ms 7744 KB Output is correct
6 Correct 87 ms 7740 KB Output is correct
7 Correct 74 ms 7604 KB Output is correct
8 Correct 102 ms 7756 KB Output is correct
9 Correct 97 ms 7776 KB Output is correct
10 Correct 111 ms 7760 KB Output is correct
11 Correct 76 ms 7764 KB Output is correct
12 Correct 133 ms 7816 KB Output is correct