Submission #637919

#	Time	Username	Problem	Language	Result	Execution time	Memory
637919		Cross_Ratio	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	799 ms	13496 KiB

sterilizing

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

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