oj.uz

답안 #637917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637917 2022-09-03T15:09:59 Z Cross_Ratio Sterilizing Spray (JOI15_sterilizing) C++14
90 / 100
 5000 ms 13388 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) {
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 6 ms 724 KB Output is correct
7 Correct 7 ms 732 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 8 ms 724 KB Output is correct
10 Correct 6 ms 724 KB Output is correct
11 Correct 6 ms 724 KB Output is correct
12 Correct 6 ms 732 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5056 ms 6648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1348 KB Output is correct
2 Correct 19 ms 5700 KB Output is correct
3 Correct 34 ms 5832 KB Output is correct
4 Correct 84 ms 4028 KB Output is correct
5 Correct 115 ms 11980 KB Output is correct
6 Correct 139 ms 12104 KB Output is correct
7 Correct 104 ms 12132 KB Output is correct
8 Correct 115 ms 11980 KB Output is correct
9 Correct 132 ms 12004 KB Output is correct
10 Correct 103 ms 11984 KB Output is correct
11 Correct 105 ms 11880 KB Output is correct
12 Correct 118 ms 11852 KB Output is correct

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 7072 KB Output is correct
2 Correct 181 ms 7348 KB Output is correct
3 Correct 229 ms 6884 KB Output is correct
4 Correct 248 ms 4812 KB Output is correct
5 Correct 265 ms 13288 KB Output is correct
6 Correct 313 ms 13316 KB Output is correct
7 Correct 262 ms 13196 KB Output is correct
8 Correct 401 ms 13336 KB Output is correct
9 Correct 353 ms 13128 KB Output is correct
10 Correct 434 ms 13184 KB Output is correct
11 Correct 291 ms 13260 KB Output is correct
12 Correct 595 ms 13388 KB Output is correct