Submission #95008

#	Time	Username	Problem	Language	Result	Execution time	Memory
95008		bogdan10bos	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	557 ms	11384 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef long long LL;

const int NMAX = 1e5;

int N, Q, K;
vector<int> init;

class SegmentTree
{
public:
    LL ans;
    vector<int> mx, mn, lzy;
    vector<LL> sum;

    void remake(int nod)
    {
        sum[nod] = sum[nod * 2] + sum[nod * 2 + 1];
        mx[nod] = max(mx[nod * 2], mx[nod * 2 + 1]);
        mn[nod] = min(mn[nod * 2], mn[nod * 2 + 1]);
    }

    void lazy(int nod, int st, int dr)
    {
        if(lzy[nod] == -1)  return;

        int mij = st + (dr - st) / 2;

        int val = lzy[nod];
        lzy[nod * 2] = lzy[nod * 2 + 1] = val;

        sum[nod * 2] = 1LL * (mij - st + 1) * val;
        mx[nod * 2] = mn[nod * 2] = val;

        sum[nod * 2 + 1] = 1LL * (dr - mij) * val;
        mx[nod * 2 + 1] = mn[nod * 2 + 1] = val;

        lzy[nod] = -1;
    }

    void B(int nod, int st, int dr)
    {
        lzy[nod] = -1;

        if(st == dr)
        {
            sum[nod] = mn[nod] = mx[nod] = init[st];
            return;
        }

        int mij = st + (dr - st) / 2;
        B(nod * 2, st, mij);
        B(nod * 2 + 1, mij + 1, dr);

        remake(nod);
    }

    void U(int nod, int st, int dr, int pos, int val)
    {
        if(st == dr)
        {
            sum[nod] = mx[nod] = mn[nod] = val;
            return;
        }

        lazy(nod, st, dr);

        int mij = st + (dr - st) / 2;
        if(pos <= mij)  U(nod * 2, st, mij, pos, val);
        else    U(nod * 2 + 1, mij + 1, dr, pos, val);

        remake(nod);
    }

    void U(int nod, int st, int dr, int sti, int dri, int val)
    {
        if(sti <= st && dr <= dri)
        {
            if(mn[nod] / val == mx[nod] / val)
            {
                mn[nod] = mx[nod] = mn[nod] / val;
                sum[nod] = 1LL * (dr - st + 1) * mn[nod];
                lzy[nod] = mn[nod];
                return;
            }

            lazy(nod, st, dr);

            int mij = st + (dr - st) / 2;
            U(nod * 2, st, mij, sti, dri, val);
            U(nod * 2 + 1, mij + 1, dr, sti, dri, val);
            remake(nod);
            return;
        }

        lazy(nod, st, dr);
        int mij = st + (dr - st) / 2;

        if(sti <= mij)  U(nod * 2, st, mij, sti, dri, val);
        if(mij < dri)   U(nod * 2 + 1, mij + 1, dr, sti, dri, val);

        remake(nod);
    }

    void Q(int nod, int st, int dr, int sti, int dri)
    {
        if(sti <= st && dr <= dri)
        {
            ans += sum[nod];
            return;
        }

        lazy(nod, st, dr);

        int mij = st + (dr - st) / 2;
        if(sti <= mij)  Q(nod * 2, st, mij, sti, dri);
        if(mij < dri)   Q(nod * 2 + 1, mij + 1, dr, sti, dri);
    }

    void build()
    {
        sum.resize(4 * N + 2);
        mx.resize(4 * N + 2);
        mn.resize(4 * N + 2);
        lzy.resize(4 * N + 2);
        B(1, 1, N);
    }

    void update(int pos, int val)
    {
        U(1, 1, N, pos, val);
    }

    void divide(int st, int dr, int K)
    {
        if(K == 1)  return;
        U(1, 1, N, st, dr, K);
    }

    LL query(int st, int dr)
    {
        ans = 0;
        Q(1, 1, N, st, dr);
        return ans;
    }
}aint;

void gen()
{
    freopen("1.in", "w", stdout);
    mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
    int N = 10, Q = 150;
    int VMAX = 100;
    int K = uniform_int_distribution<int>(2, 10)(g);

    printf("%d %d %d\n", N, Q, K);
    for(int i = 1; i <= N; i++)
        printf("%d ", uniform_int_distribution<int>(0, VMAX)(g));
    printf("\n");
    auto uid = uniform_int_distribution<int>(1, N);
    for(int i = 1; i <= Q; i++)
    {
        int op = g() % 3 + 1;
        if(op == 1)
        {
            int pos = uid(g);
            printf("%d %d %d\n", op, pos, uniform_int_distribution<int>(0, VMAX)(g));
        }
        else
        {
            int st = uid(g), dr = uid(g);
            if(st > dr) swap(st, dr);
            printf("%d %d %d\n", op, st, dr);
        }
    }
    exit(0);
}

int main()
{
    //gen();

    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d%d", &N, &Q, &K);
    init.resize(N + 2);
    for(int i = 1; i <= N; i++) scanf("%d", &init[i]);
    aint.build();
    for(int q = 1; q <= Q; q++)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int pos, val;
            scanf("%d%d", &pos, &val);
            aint.update(pos, val);

//            init[pos] = val;
        }
        else if(op == 2)
        {
            int st, dr;
            scanf("%d%d", &st, &dr);
            aint.divide(st, dr, K);

//            for(int i = st; i <= dr; i++)   init[i] /= K;
        }
        else if(op == 3)
        {
            int st, dr;
            scanf("%d%d", &st, &dr);
            LL ans = aint.query(st, dr);
            printf("%lld\n", ans);

//            for(int i = st; i <= dr; i++)   ans -= init[i];
//            if(ans != 0)
//            {
//                cerr << "Assertion failed!"  << '\n';
//                ans++;
//                ans--;
//            }
        }
    }

    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'void gen()':
sterilizing.cpp:155:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &Q, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:195:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &init[i]);
                                 ~~~~~^~~~~~~~~~~~~~~~
sterilizing.cpp:200:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &op);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp:204:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &pos, &val);
             ~~~~~^~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:212:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &st, &dr);
             ~~~~~^~~~~~~~~~~~~~~~~~
sterilizing.cpp:220:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &st, &dr);
             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75