oj.uz

Submission #637919

# Submission time Handle Problem Language Result Execution time Memory
637919 2022-09-03T15:14:10 Z Cross_Ratio Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 799 ms 13496 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
    ll sum;
    ll mi, ma;
    ll n, p;
    Node() {
        sum = mi = ma = 0;
        n = -1, p = 0;
    }
    Node(ll v) {
        sum = mi = ma = v;
        n = -1, p = 0;
    }
};
struct SegTree {
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    Node f(Node x, Node y) {
        Node c;
        c.sum = x.sum + y.sum;
        c.ma = max(x.ma, y.ma);
        c.mi = min(x.mi, y.mi);
        c.n = -1;
        c.p = 0;
        return c;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = f(seg[2*i], seg[2*i+1]);
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].n != -1) {
            seg[n].ma = seg[n].mi = (seg[n].n + seg[n].p);
            seg[n].sum = seg[n].ma * (ne - ns);
            if(n<MAX/2) {
                seg[2*n].n = seg[n].n;
                seg[2*n].p = seg[n].p;
                seg[2*n+1].n = seg[n].n;
                seg[2*n+1].p = seg[n].p;
            }
            seg[n].n = -1;
            seg[n].p = 0;
        }
        else {
            seg[n].ma += seg[n].p;
            seg[n].mi += seg[n].p;
            seg[n].sum += seg[n].p * (ne - ns);
            if(n<MAX/2) {
                seg[2*n].p += seg[n].p;
                seg[2*n+1].p += seg[n].p;
            }
            seg[n].p = 0;
        }
    }
    void add1(int s, int e, ll d, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p += d;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add1(s, e, d, 2*n, ns, mid);
        add1(s, e, d, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
    }
    void add2(int s, int e, ll d, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            if(seg[n].ma / d == seg[n].mi / d) {
                seg[n].n = seg[n].ma / d;
                prop(n,ns,ne);
                return;
            }// dk-1, dk -> k-1, k
            else if(seg[n].mi + 1 == seg[n].ma) {
                seg[n].p -= (d-1) * (seg[n].ma / d);
                prop(n,ns,ne);
                return;
            }
        }
        int mid = ns + ne >> 1;
        add2(s, e, d, 2*n, ns, mid);
        add2(s, e, d, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
    }
    ll sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n].sum;
        int mid = ns + ne >> 1;
        return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
    }
};
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, Q, K;
    cin >> N >> Q >> K;
    SegTree tree(N+5);
    int MAX = tree.MAX;
    int i, j;
    for(i=0;i<N;i++) {
        ll a;
        cin >> a;
        tree.seg[i+MAX/2] = Node(a);
    }
    tree.cons();
    while(Q--) {
        ll a, b, c;
        cin >> a >> b >>c;
        b--;
        if(a==1) {
            ll val = tree.sum(b, b+1, 1, 0, MAX/2);
            tree.add1(b, b+1, c - val, 1, 0, MAX/2);
        }
        if(a==2) {
            if(K != 1) tree.add2(b, c, K, 1, 0, MAX/2);
        }
        if(a==3) {
            cout << tree.sum(b, c, 1, 0, MAX/2) << '\n';
        }
    }
}

Compilation message

sterilizing.cpp: In member function 'void SegTree::add1(int, int, ll, int, int, int)':
sterilizing.cpp:72:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
sterilizing.cpp: In member function 'void SegTree::add2(int, int, ll, int, int, int)':
sterilizing.cpp:92:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
sterilizing.cpp: In member function 'll SegTree::sum(int, int, int, int, int)':
sterilizing.cpp:101:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:113:12: warning: unused variable 'j' [-Wunused-variable]
  113 |     int i, j;
      |            ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 7 ms 552 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 720 KB Output is correct
7 Correct 7 ms 728 KB Output is correct
8 Correct 7 ms 720 KB Output is correct
9 Correct 8 ms 712 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 6 ms 712 KB Output is correct
12 Correct 12 ms 732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6812 KB Output is correct
2 Correct 74 ms 7448 KB Output is correct
3 Correct 59 ms 12424 KB Output is correct
4 Correct 68 ms 13000 KB Output is correct
5 Correct 95 ms 13452 KB Output is correct
6 Correct 89 ms 13420 KB Output is correct
7 Correct 129 ms 13496 KB Output is correct
8 Correct 93 ms 13388 KB Output is correct
9 Correct 85 ms 13352 KB Output is correct
10 Correct 78 ms 13348 KB Output is correct
11 Correct 85 ms 13276 KB Output is correct
12 Correct 79 ms 13328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1176 KB Output is correct
2 Correct 19 ms 5716 KB Output is correct
3 Correct 32 ms 5716 KB Output is correct
4 Correct 88 ms 3168 KB Output is correct
5 Correct 122 ms 10872 KB Output is correct
6 Correct 122 ms 10856 KB Output is correct
7 Correct 74 ms 10996 KB Output is correct
8 Correct 123 ms 10856 KB Output is correct
9 Correct 107 ms 10860 KB Output is correct
10 Correct 120 ms 10864 KB Output is correct
11 Correct 109 ms 10872 KB Output is correct
12 Correct 139 ms 10872 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 5792 KB Output is correct
2 Correct 179 ms 5904 KB Output is correct
3 Correct 222 ms 5912 KB Output is correct
4 Correct 234 ms 3492 KB Output is correct
5 Correct 302 ms 11100 KB Output is correct
6 Correct 311 ms 11100 KB Output is correct
7 Correct 281 ms 11104 KB Output is correct
8 Correct 391 ms 11124 KB Output is correct
9 Correct 356 ms 11088 KB Output is correct
10 Correct 417 ms 11156 KB Output is correct
11 Correct 290 ms 11240 KB Output is correct
12 Correct 799 ms 11160 KB Output is correct