Submission #25152

#	Time	Username	Problem	Language	Result	Execution time	Memory
25152		tlwpdus	Sterilizing Spray (JOI15_sterilizing)	C++14	15 / 100	5000 ms	5568 KiB

sterilizing

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75