oj.uz

Submission #153954

# Submission time Handle Problem Language Result Execution time Memory
153954 2019-09-17T14:55:54 Z georgerapeanu Sterilizing Spray (JOI15_sterilizing) C++11
10 / 100
 214 ms 9464 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(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
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 476 KB Output is correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5724 KB Output is correct
2 Correct 78 ms 5352 KB Output is correct
3 Correct 76 ms 8444 KB Output is correct
4 Correct 96 ms 8952 KB Output is correct
5 Correct 115 ms 9360 KB Output is correct
6 Correct 113 ms 9464 KB Output is correct
7 Correct 112 ms 9316 KB Output is correct
8 Correct 124 ms 9348 KB Output is correct
9 Correct 106 ms 9260 KB Output is correct
10 Correct 107 ms 9216 KB Output is correct
11 Correct 105 ms 9228 KB Output is correct
12 Correct 106 ms 9256 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1144 KB Output is correct
2 Incorrect 24 ms 3704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5076 KB Output is correct
2 Incorrect 214 ms 5276 KB Output isn't correct
3 Halted 0 ms 0 KB -