oj.uz

답안 #518601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518601 2022-01-24T09:06:22 Z XEMPLI5 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 599 ms 16304 KB 
#include <bits/stdc++.h>
using namespace std;

#define gc getchar_unlocked
#define fo(i, n) for (int i = 0; i < n; i++)
#define rfo(i, n) for (int i = n - 1; i >= 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define si(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define ss(s) scanf("%s", s)
#define pi(x) printf("%d\n", x)
#define pl(x) printf("%lld\n", x)
#define ps(s) printf("%s\n", s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626

typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

int mpow(int base, int exp);
void dfs(int u, int par);

const int mod = 1'000'000'007;
const int N = 1e5 + 10, M = N;

vi g[N];
ll a[N], ans[N];
ll seg[4 * N];

void build(int l, int r, int pos)
{
    if (l == r)
    {
        seg[pos] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * pos);
    build(mid + 1, r, 2 * pos + 1);
    seg[pos] = seg[2 * pos] + seg[2 * pos + 1];
}

void update(int l, int r, int pos, int qpos, int qv)
{
    if (l == r)
    {
        seg[pos] = qv;
        a[qpos] = qv;
        return;
    }
    int mid = (l + r) / 2;
    if (qpos <= mid)
    {
        update(l, mid, 2 * pos, qpos, qv);
    }
    else
    {
        update(mid + 1, r, 2 * pos + 1, qpos, qv);
    }
    seg[pos] = seg[2 * pos] + seg[2 * pos + 1];
}

ll query(int l, int r, int pos, int ql, int qr)
{
    // no intersection
    if (ql > r || qr < l)
        return 0;
    // full
    if (l >= ql && r <= qr)
        return seg[pos];
    // parital
    int mid = (l + r) / 2;
    return query(l, mid, 2 * pos, ql, qr) + query(mid + 1, r, 2 * pos + 1, ql, qr);
}

void solve()
{
    int n, q, k;
    cin >> n >> q >> k;
    fo(i, n) cin >> a[i];
    build(0, n - 1, 1);
    set<int> vals;
    fo(i, n) vals.insert(i);
    fo(i, q)
    {
        ll s, t, u;
        cin >> s >> t >> u;
        if (s == 1)
        {
            update(0, n - 1, 1, t - 1, u);
            if (u == 0 && vals.find(t - 1) != vals.end())
                vals.erase(vals.find(t - 1));
            else
                vals.insert(t - 1);
        }
        else if (s == 2)
        {
            if (k == 1)
                continue;
            auto it = vals.lower_bound(t - 1);
            set<int> erasepos;
            while (it != vals.end() && *it < u)
            {
                int nv = a[*it] / k;
                if (nv == 0)
                    erasepos.insert(*it);
                update(0, n - 1, 1, *it, nv);
                it++;
            }
            for (auto e : erasepos)
                vals.erase(vals.find(e));
        }
        else
        {
            cout << query(0, n - 1, 1, t - 1, u - 1) << '\n';
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;
    int cs = 0;
    while (t - cs)
    {
        solve();
        cs++;
    }

    return 0;
}

int mpow(int base, int exp)
{
    base %= mod;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = ((ll)result * base) % mod;
        base = ((ll)base * base) % mod;
        exp >>= 1;
    }
    return result;
}

void ipgraph(int n, int m)
{
    int u, v;
    while (m--)
    {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }
}

void dfs(int u, int par)
{
    for (int v : g[u])
    {
        if (v == par)
            continue;
        dfs(v, u);
    }
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 4 ms 2804 KB Output is correct
4 Correct 8 ms 2784 KB Output is correct
5 Correct 9 ms 2892 KB Output is correct
6 Correct 7 ms 2892 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 9 ms 2892 KB Output is correct
9 Correct 10 ms 2892 KB Output is correct
10 Correct 9 ms 2892 KB Output is correct
11 Correct 8 ms 2900 KB Output is correct
12 Correct 8 ms 2892 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 6788 KB Output is correct
2 Correct 52 ms 5828 KB Output is correct
3 Correct 80 ms 9184 KB Output is correct
4 Correct 76 ms 10564 KB Output is correct
5 Correct 82 ms 10824 KB Output is correct
6 Correct 85 ms 10696 KB Output is correct
7 Correct 84 ms 10732 KB Output is correct
8 Correct 87 ms 10740 KB Output is correct
9 Correct 81 ms 10692 KB Output is correct
10 Correct 77 ms 10796 KB Output is correct
11 Correct 83 ms 10780 KB Output is correct
12 Correct 86 ms 10784 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 3600 KB Output is correct
2 Correct 33 ms 6604 KB Output is correct
3 Correct 41 ms 7000 KB Output is correct
4 Correct 57 ms 5640 KB Output is correct
5 Correct 128 ms 12092 KB Output is correct
6 Correct 108 ms 10984 KB Output is correct
7 Correct 89 ms 11716 KB Output is correct
8 Correct 120 ms 12856 KB Output is correct
9 Correct 111 ms 16120 KB Output is correct
10 Correct 123 ms 16172 KB Output is correct
11 Correct 133 ms 16196 KB Output is correct
12 Correct 112 ms 16304 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 6792 KB Output is correct
2 Correct 163 ms 6848 KB Output is correct
3 Correct 264 ms 6284 KB Output is correct
4 Correct 172 ms 5216 KB Output is correct
5 Correct 262 ms 10780 KB Output is correct
6 Correct 318 ms 10488 KB Output is correct
7 Correct 250 ms 10688 KB Output is correct
8 Correct 436 ms 10580 KB Output is correct
9 Correct 346 ms 12616 KB Output is correct
10 Correct 439 ms 11456 KB Output is correct
11 Correct 341 ms 12464 KB Output is correct
12 Correct 599 ms 10440 KB Output is correct