제출 #518594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
518594		XEMPLI5	Sterilizing Spray (JOI15_sterilizing)	C++17	90 / 100	641 ms	14112 KiB

sterilizing

#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, 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.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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75