oj.uz

Submission #25152

# Submission time Handle Problem Language Result Execution time Memory
25152 2017-06-20T08:32:16 Z tlwpdus Sterilizing Spray (JOI15_sterilizing) C++14
15 / 100
 5000 ms 5568 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, q;
ll arr[100100];
ll k;

ll tree[270000];
int key = 131072;
void upd(int idx, ll val) {
    idx+=key;
    tree[idx] = val;
    idx>>=1;
    while(idx>0) {
        tree[idx] = tree[idx*2]+tree[idx*2+1];
        idx>>=1;
    }
}
ll getv(int s, int e) {
    ll res = 0;
    s+=key; e+=key;
    while(s<=e) {
        if (s&1) res += tree[s++];
        if (~e&1) res += tree[e--];
        s>>=1;e>>=1;
    }
    return res;
}
void solve1() {
    int i;
    for (i=0;i<n;i++) upd(i,arr[i]);
    for (i=0;i<q;i++) {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        if (a==1) upd(b-1,c);
        else if (a==3) printf("%lld\n",getv(b-1,c-1));
    }
}

ll power[40];
int maxcnt;
const int SZ = 55;
int nb;
ll sum[2000], rem[2000][40], cnt[2000];

void recalc(int i) {
    int j, l;
    sum[i] = cnt[i] = 0;
    for (j=0;j<maxcnt;j++) rem[i][j] = 0;
    for (j=0;j<SZ&&i*SZ+j<n;j++) {
        int idx = i*SZ+j;
        sum[i] += arr[idx];
        for (l=0;l<maxcnt;l++) {
            rem[i][l] += (arr[idx]/power[l])%k;
        }
    }
}
void doupd(int i, int s, int e) {
    int j;
    for (j=0;j<SZ&&i*SZ+j<n;j++) {
        int idx = i*SZ+j;
        arr[idx] /= power[cnt[i]];
    }
    for (j=s;j<=e&&j<SZ&&i*SZ+j<n;j++) {
        int idx = i*SZ+j;
        arr[idx] /= k;
    }
}
void solve() {
    int i, j, l;
    power[0] = 1;
    for (i=1;power[i-1]<=1000000000LL;i++) power[i] = power[i-1]*k;
    maxcnt = i;
    nb = (n-1)/SZ+1;
    for (i=0;i<nb;i++) {
        for (j=0;j<SZ&&i*SZ+j<n;j++) {
            int idx = i*SZ+j;
            sum[i] += arr[idx];
            for (l=0;l<maxcnt;l++) {
                rem[i][l] += (arr[idx]/power[l])%k;
            }
        }
    }
    for (i=0;i<q;i++) {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        if (a==1) {
            b--;
            int bl = b/SZ;
            doupd(bl,-1,-2);
            arr[b] = c;
            recalc(bl);
        }
        else if (a==2) {
            b--; c--;
            int bl = b/SZ, cl = c/SZ;
            for (j=bl+1;j<cl;j++) {
                sum[j] = (sum[j]-rem[j][cnt[j]])/k;
                cnt[j]++;
                if (cnt[j]>=maxcnt) cnt[j] = maxcnt-1;
            }
            if (bl!=cl) {
                doupd(bl,b%SZ,SZ-1);
                recalc(bl);
                doupd(cl,0,c%SZ);
                recalc(cl);
            }
            else {
                doupd(bl,b%SZ,c%SZ);
                recalc(bl);
            }
        }
        else if (a==3) {
            b--; c--;
            int bl = b/SZ, cl = c/SZ; ll res = 0;
            for (j=bl+1;j<cl;j++) {
                res += sum[j];
            }
            if (bl!=cl) {
                doupd(bl,-1,-2);
                recalc(bl);
                for (j=b;j/SZ==bl;j++) res += arr[j];
                doupd(cl,-1,-2);
                recalc(cl);
                for (j=cl*SZ;j<=c;j++) res += arr[j];
            }
            else {
                doupd(bl,-1,-2);
                recalc(bl);
                for (j=b;j<=c;j++) res+=arr[j];
            }
            printf("%lld\n",res);
        }
    }
}

int main() {
    int i;

    //freopen("input","r",stdin);

    scanf("%d%d%d",&n,&q,&k);
    for (i=0;i<n;i++) scanf("%lld",&arr[i]);
    if (k==1) solve1();
    else solve();

    return 0;
}

Compilation message

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:145:28: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll* {aka long long int*}' [-Wformat=]
     scanf("%d%d%d",&n,&q,&k);
                            ^
sterilizing.cpp: In function 'void solve1()':
sterilizing.cpp:37:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
                                 ^
sterilizing.cpp: In function 'void solve()':
sterilizing.cpp:89:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
                                 ^
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:145:29: 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:146:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%lld",&arr[i]);
                                            ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5568 KB Output is correct
2 Correct 0 ms 5568 KB Output is correct
3 Correct 6 ms 5568 KB Output is correct
4 Correct 206 ms 5568 KB Output is correct
5 Correct 106 ms 5568 KB Output is correct
6 Correct 83 ms 5568 KB Output is correct
7 Correct 103 ms 5568 KB Output is correct
8 Correct 99 ms 5568 KB Output is correct
9 Correct 149 ms 5568 KB Output is correct
10 Correct 106 ms 5568 KB Output is correct
11 Correct 99 ms 5568 KB Output is correct
12 Correct 116 ms 5568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5568 KB Output is correct
2 Correct 66 ms 5568 KB Output is correct
3 Correct 43 ms 5568 KB Output is correct
4 Correct 73 ms 5568 KB Output is correct
5 Correct 66 ms 5568 KB Output is correct
6 Correct 89 ms 5568 KB Output is correct
7 Correct 69 ms 5568 KB Output is correct
8 Correct 93 ms 5568 KB Output is correct
9 Correct 69 ms 5568 KB Output is correct
10 Correct 73 ms 5568 KB Output is correct
11 Correct 83 ms 5568 KB Output is correct
12 Correct 59 ms 5568 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1383 ms 5568 KB Output is correct
2 Correct 773 ms 5568 KB Output is correct
3 Correct 749 ms 5568 KB Output is correct
4 Correct 2609 ms 5568 KB Output is correct
5 Correct 4046 ms 5568 KB Output is correct
6 Execution timed out 5000 ms 5568 KB Execution timed out
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2113 ms 5568 KB Output is correct
2 Correct 2279 ms 5568 KB Output is correct
3 Correct 3723 ms 5568 KB Output is correct
4 Correct 3879 ms 5568 KB Output is correct
5 Correct 3119 ms 5568 KB Output is correct
6 Correct 4013 ms 5568 KB Output is correct
7 Correct 3006 ms 5568 KB Output is correct
8 Execution timed out 5000 ms 5568 KB Execution timed out
9 Halted 0 ms 0 KB -