oj.uz

Submission #153966

# Submission time Handle Problem Language Result Execution time Memory
153966 2019-09-17T15:21:09 Z georgerapeanu Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 702 ms 9392 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

struct node_t {
    long long sum;
    int cnt;
    int mi;
    int ma;
    int lazy;

    node_t operator + (const node_t &other)const {
        node_t ans;
        ans.sum = this->sum + other.sum;
        ans.cnt = this->cnt + other.cnt;
        ans.mi = min(this->mi,other.mi);
        ans.ma = max(this->ma,other.ma);
        ans.lazy = 0;
        return ans;
    }
};

int n,q,k;

node_t aint[4 * NMAX + 5];

void propag(int nod,int st,int dr) {
    if(st == dr || aint[nod].lazy == 0) {
        return ;
    }

    aint[2 * nod].lazy += aint[nod].lazy;
    aint[2 * nod].mi += aint[nod].lazy;
    aint[2 * nod].ma += aint[nod].lazy;
    aint[2 * nod].sum += 1LL * aint[2 * nod].cnt * aint[nod].lazy;

    aint[2 * nod + 1].lazy += aint[nod].lazy;
    aint[2 * nod + 1].mi += aint[nod].lazy;
    aint[2 * nod + 1].ma += aint[nod].lazy;
    aint[2 * nod + 1].sum += 1LL * aint[2 * nod + 1].cnt * aint[nod].lazy;

    aint[nod].lazy = 0;
}

void build(int nod,int st,int dr) {
    if(st == dr) {
        int val;
        scanf("%d",&val);
        aint[nod].sum = aint[nod].mi = aint[nod].ma = val;
        aint[nod].cnt = 1;
        aint[nod].lazy = 0;
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_pos(int nod,int st,int dr,int pos,int val) {
    propag(nod,st,dr);

    if(st > pos || dr < pos) {
        return ;
    }

    if(st == dr) {
        aint[nod].sum = aint[nod].mi = aint[nod].ma = val;
        return ;
    }

    int mid = (st + dr) / 2;

    update_pos(nod * 2,st,mid,pos,val);
    update_pos(nod * 2 + 1,mid + 1,dr,pos,val);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_range(int nod,int st,int dr,int l,int r) {
    propag(nod,st,dr);

    if(dr < l || st > r) {
        return ;
    }

    if(l <= st && dr <= r && aint[nod].ma - (aint[nod].ma / k) == aint[nod].mi - (aint[nod].mi / k)) {
        aint[nod].lazy += -aint[nod].ma + (aint[nod].ma / k);
        aint[nod].mi += -aint[nod].ma + (aint[nod].ma / k);
        aint[nod].sum += 1LL * aint[nod].cnt * (-aint[nod].ma + (aint[nod].ma / k));
        aint[nod].ma += -aint[nod].ma + (aint[nod].ma / k);
        return ;
    }

    int mid = (st + dr) / 2;

    update_range(nod * 2,st,mid,l,r);
    update_range(nod * 2 + 1,mid + 1,dr,l,r);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

long long query(int nod,int st,int dr,int l,int r) {
    propag(nod,st,dr);

    if(dr < l || st > r) {
        return 0;
    }

    if(l <= st && dr <= r) {
        return aint[nod].sum;
    }

    int mid = (st + dr) / 2;

    return query(nod * 2,st,mid,l,r) + query(nod * 2 + 1,mid + 1,dr,l,r);
}

int main() {

    scanf("%d %d %d",&n,&q,&k);

    build(1,1,n);

    while(q--) {
        int t,a,b;

        scanf("%d %d %d",&t,&a,&b);

        if(t == 1) {
            update_pos(1,1,n,a,b);
        }
        else if(t == 2) {
            update_range(1,1,n,a,b);
        }
        else {
            printf("%lld\n",query(1,1,n,a,b));
        }
    }

    return 0;
}

Compilation message

sterilizing.cpp: In function 'void build(int, int, int)':
sterilizing.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&val);
         ~~~~~^~~~~~~~~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:127: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:134:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&t,&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 10 ms 504 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 10 ms 636 KB Output is correct
9 Correct 11 ms 632 KB Output is correct
10 Correct 10 ms 632 KB Output is correct
11 Correct 10 ms 632 KB Output is correct
12 Correct 10 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 5820 KB Output is correct
2 Correct 110 ms 5496 KB Output is correct
3 Correct 99 ms 8440 KB Output is correct
4 Correct 131 ms 8908 KB Output is correct
5 Correct 158 ms 9208 KB Output is correct
6 Correct 160 ms 9184 KB Output is correct
7 Correct 157 ms 9208 KB Output is correct
8 Correct 163 ms 9280 KB Output is correct
9 Correct 138 ms 9208 KB Output is correct
10 Correct 138 ms 9336 KB Output is correct
11 Correct 139 ms 9336 KB Output is correct
12 Correct 138 ms 9384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1144 KB Output is correct
2 Correct 28 ms 3704 KB Output is correct
3 Correct 37 ms 3804 KB Output is correct
4 Correct 101 ms 3192 KB Output is correct
5 Correct 140 ms 7940 KB Output is correct
6 Correct 141 ms 7916 KB Output is correct
7 Correct 128 ms 8184 KB Output is correct
8 Correct 140 ms 7928 KB Output is correct
9 Correct 129 ms 7800 KB Output is correct
10 Correct 128 ms 7800 KB Output is correct
11 Correct 129 ms 7936 KB Output is correct
12 Correct 131 ms 7928 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 5016 KB Output is correct
2 Correct 228 ms 5316 KB Output is correct
3 Correct 293 ms 4856 KB Output is correct
4 Correct 299 ms 3892 KB Output is correct
5 Correct 343 ms 9148 KB Output is correct
6 Correct 399 ms 9312 KB Output is correct
7 Correct 326 ms 9216 KB Output is correct
8 Correct 499 ms 9392 KB Output is correct
9 Correct 434 ms 9048 KB Output is correct
10 Correct 507 ms 9140 KB Output is correct
11 Correct 355 ms 9180 KB Output is correct
12 Correct 702 ms 9148 KB Output is correct