oj.uz

Submission #1071019

# Submission time Handle Problem Language Result Execution time Memory
1071019 2024-08-23T00:36:44 Z Boycl07 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9320 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)
        {
            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:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("note.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         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 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4588 ms 5536 KB Output is correct
2 Correct 3074 ms 4376 KB Output is correct
3 Correct 4601 ms 6724 KB Output is correct
4 Execution timed out 5051 ms 8248 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1172 KB Output is correct
2 Correct 10 ms 2140 KB Output is correct
3 Correct 12 ms 2484 KB Output is correct
4 Correct 22 ms 2392 KB Output is correct
5 Correct 37 ms 5460 KB Output is correct
6 Correct 40 ms 5456 KB Output is correct
7 Execution timed out 5065 ms 4836 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5200 KB Output is correct
2 Correct 51 ms 5312 KB Output is correct
3 Correct 52 ms 4396 KB Output is correct
4 Correct 67 ms 4180 KB Output is correct
5 Correct 103 ms 9320 KB Output is correct
6 Correct 89 ms 9044 KB Output is correct
7 Correct 77 ms 9016 KB Output is correct
8 Correct 102 ms 9040 KB Output is correct
9 Correct 82 ms 9032 KB Output is correct
10 Correct 96 ms 9076 KB Output is correct
11 Correct 76 ms 9024 KB Output is correct
12 Correct 115 ms 9056 KB Output is correct