oj.uz

Submission #373340

# Submission time Handle Problem Language Result Execution time Memory
373340 2021-03-04T07:57:38 Z BartolM Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 256 ms 9588 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 7 ms 620 KB Output is correct
6 Correct 6 ms 620 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 4 ms 620 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 8 ms 620 KB Output is correct
11 Correct 6 ms 620 KB Output is correct
12 Correct 5 ms 620 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5740 KB Output is correct
2 Correct 62 ms 4588 KB Output is correct
3 Correct 55 ms 7404 KB Output is correct
4 Correct 71 ms 9068 KB Output is correct
5 Correct 80 ms 9588 KB Output is correct
6 Correct 81 ms 9580 KB Output is correct
7 Correct 83 ms 9580 KB Output is correct
8 Correct 85 ms 9580 KB Output is correct
9 Correct 78 ms 9452 KB Output is correct
10 Correct 77 ms 9452 KB Output is correct
11 Correct 78 ms 9452 KB Output is correct
12 Correct 77 ms 9456 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1132 KB Output is correct
2 Correct 19 ms 2412 KB Output is correct
3 Correct 23 ms 2540 KB Output is correct
4 Correct 45 ms 2540 KB Output is correct
5 Correct 71 ms 5868 KB Output is correct
6 Correct 71 ms 5792 KB Output is correct
7 Correct 72 ms 5896 KB Output is correct
8 Correct 69 ms 5740 KB Output is correct
9 Correct 66 ms 5612 KB Output is correct
10 Correct 75 ms 5612 KB Output is correct
11 Correct 65 ms 5612 KB Output is correct
12 Correct 81 ms 5888 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 5256 KB Output is correct
2 Correct 87 ms 5484 KB Output is correct
3 Correct 99 ms 4460 KB Output is correct
4 Correct 101 ms 4460 KB Output is correct
5 Correct 144 ms 9324 KB Output is correct
6 Correct 169 ms 9452 KB Output is correct
7 Correct 146 ms 9324 KB Output is correct
8 Correct 196 ms 9324 KB Output is correct
9 Correct 187 ms 9324 KB Output is correct
10 Correct 201 ms 9196 KB Output is correct
11 Correct 154 ms 9196 KB Output is correct
12 Correct 256 ms 9196 KB Output is correct