oj.uz

답안 #518594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518594 2022-01-24T08:56:22 Z XEMPLI5 Sterilizing Spray (JOI15_sterilizing) C++17
90 / 100
 641 ms 14112 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, 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2680 KB Output is correct
3 Correct 4 ms 2768 KB Output is correct
4 Correct 9 ms 2836 KB Output is correct
5 Correct 10 ms 2900 KB Output is correct
6 Correct 11 ms 2900 KB Output is correct
7 Correct 10 ms 2900 KB Output is correct
8 Correct 10 ms 2956 KB Output is correct
9 Correct 13 ms 2940 KB Output is correct
10 Correct 9 ms 2900 KB Output is correct
11 Correct 9 ms 2940 KB Output is correct
12 Correct 10 ms 2896 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 7028 KB Output is correct
2 Correct 62 ms 6128 KB Output is correct
3 Correct 67 ms 9496 KB Output is correct
4 Correct 75 ms 10760 KB Output is correct
5 Correct 96 ms 10840 KB Output is correct
6 Correct 90 ms 10868 KB Output is correct
7 Correct 88 ms 10836 KB Output is correct
8 Correct 111 ms 10868 KB Output is correct
9 Correct 83 ms 10868 KB Output is correct
10 Correct 83 ms 10880 KB Output is correct
11 Correct 85 ms 10916 KB Output is correct
12 Correct 88 ms 10932 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 6432 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 7056 KB Output is correct
2 Correct 155 ms 7028 KB Output is correct
3 Correct 285 ms 6484 KB Output is correct
4 Correct 173 ms 5444 KB Output is correct
5 Correct 281 ms 10900 KB Output is correct
6 Correct 316 ms 12084 KB Output is correct
7 Correct 274 ms 12252 KB Output is correct
8 Correct 428 ms 12100 KB Output is correct
9 Correct 378 ms 14112 KB Output is correct
10 Correct 406 ms 13124 KB Output is correct
11 Correct 281 ms 14060 KB Output is correct
12 Correct 641 ms 11972 KB Output is correct