oj.uz

Submission #1071020

# Submission time Handle Problem Language Result Execution time Memory
1071020 2024-08-23T00:39:07 Z Boycl07 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 108 ms 9096 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "BAI1"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 1e5 + 3;
const int M = 1e3;
const int LOG = 50;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n, q, k;

ll bit[N];
int a[N];

void update(int u, int v)
{
    for(; u <= n; u += u & -u) bit[u] += v;
}

ll get(int u)
{
    ll res = 0;
    for(; u; u -= u & -u) res += bit[u];
    return res;
}

set<int> s;

void solve()
{
    cin >> n >> q >> k;
    rep(i, n)
    {
        cin >> a[i];
        if(a[i]) s.insert(i);
        update(i, a[i]);
    }

    rep(i, q)
    {
        int type, x, y;
        cin >> type >> x >> y;
        if(type == 1)
        {
            if(s.find(x) !=  s.end()) s.erase(x);
            update(x, y - a[x]);
            a[x] = y;
            if(a[x] > 0) s.insert(x);
        } else if(type == 2)
        {
            if(k > 1)
            {
                auto u = s.lower_bound(x);
                vector<int> tmp;
                while(u != s.end() && *u <= y)
                {
                    int idx = *u;
                    int new_val = a[idx] / k;
                    update(idx, new_val - a[idx]);
                    a[idx] = new_val;
                    if(a[idx] == 0) tmp.pb(idx);
                    ++u;
                }
                for(int idx : tmp) s.erase(idx);
            }
        } else cout << get(y) - get(x - 1) << endl;

    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    if(fopen("note.inp", "r"))
    {
        freopen("note.inp", "r", stdin);
        freopen("note.out", "w", stdout);
    }

    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("note.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("note.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3672 KB Output is correct
2 Correct 34 ms 2760 KB Output is correct
3 Correct 46 ms 5208 KB Output is correct
4 Correct 50 ms 6612 KB Output is correct
5 Correct 59 ms 9024 KB Output is correct
6 Correct 56 ms 9044 KB Output is correct
7 Correct 57 ms 9040 KB Output is correct
8 Correct 60 ms 9080 KB Output is correct
9 Correct 57 ms 9040 KB Output is correct
10 Correct 56 ms 9096 KB Output is correct
11 Correct 55 ms 9044 KB Output is correct
12 Correct 57 ms 9040 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 9 ms 1944 KB Output is correct
3 Correct 12 ms 2052 KB Output is correct
4 Correct 23 ms 1404 KB Output is correct
5 Correct 35 ms 3928 KB Output is correct
6 Correct 37 ms 3932 KB Output is correct
7 Correct 38 ms 4436 KB Output is correct
8 Correct 39 ms 5456 KB Output is correct
9 Correct 38 ms 5248 KB Output is correct
10 Correct 34 ms 5384 KB Output is correct
11 Correct 32 ms 5388 KB Output is correct
12 Correct 32 ms 5384 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3580 KB Output is correct
2 Correct 46 ms 3632 KB Output is correct
3 Correct 51 ms 3096 KB Output is correct
4 Correct 48 ms 2392 KB Output is correct
5 Correct 76 ms 6480 KB Output is correct
6 Correct 83 ms 6484 KB Output is correct
7 Correct 77 ms 6480 KB Output is correct
8 Correct 95 ms 6468 KB Output is correct
9 Correct 84 ms 6888 KB Output is correct
10 Correct 87 ms 6764 KB Output is correct
11 Correct 76 ms 6772 KB Output is correct
12 Correct 108 ms 6632 KB Output is correct