Submission #373340

#	Time	Username	Problem	Language	Result	Execution time	Memory
373340		BartolM	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	256 ms	9588 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;

int n, q, k;
ll p[N], F[N];
set <int> S;

void update(int x, ll val) { //postavi na val
//    printf("postavljam %d na %lld\n", x, val);
    if (p[x]==0 && val) S.insert(x);
    else if (val==0 && p[x]) S.erase(x);

    swap(p[x], val);
    val=p[x]-val;
//    printf("+=%lld\n", val);
    for (; x<=n; x+=x&-x) F[x]+=val;
}

ll query(int x) {
    ll ret=0;
    for (; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

void slucaj() {
    for (int i=0; i<q; ++i) {
        int br, a, b;
        scanf("%d %d %d", &br, &a, &b);
        if (br==1) update(a, b);
        if (br==3) printf("%lld\n", query(b)-query(a-1));
    }
}

void solve() {
    for (int i=0; i<q; ++i) {
        int br, a, b;
        scanf("%d %d %d", &br, &a, &b);
        if (br==1) update(a, b);
        else if (br==2) {
            set <int>::iterator it=S.lower_bound(a), nx;
            while (it!=S.end() && *it<=b) {
                nx=it; nx++;
                update(*it, p[*it]/k);
                it=nx;
            }
        }
        else printf("%lld\n", query(b)-query(a-1));
    }
}

void load() {
    scanf("%d %d %d", &n, &q, &k);
    for (int i=1; i<=n; ++i) {
        int x;
        scanf("%d", &x);
        update(i, x);
    }
}

int main() {
    load();
    if (k==1) slucaj();
    else solve();
    return 0;
}

Compilation message (stderr)

sterilizing.cpp: In function 'void slucaj()':
sterilizing.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         scanf("%d %d %d", &br, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'void solve()':
sterilizing.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%d %d %d", &br, &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp: In function 'void load()':
sterilizing.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |     scanf("%d %d %d", &n, &q, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

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