Submission #697994

#	Time	Username	Problem	Language	Result	Execution time	Memory
697994		Cross_Ratio	단층 (JOI16_ho_t5)	C++14	100 / 100	684 ms	28804 KiB

2016_ho_t5

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
array<int, 3> A[200005];//0 is type ->, 1 is type up
struct SegTree {
    struct Node {
        int ma, p;
        Node():ma(-INF), p(0){}
        Node(int _m) : ma(_m), p(0) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i].ma = max(seg[2*i].ma, seg[2*i+1].ma);
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].p) {
            seg[n].ma += seg[n].p;
            if(n<MAX/2) {
                seg[2*n].p += seg[n].p;
                seg[2*n+1].p += seg[n].p;
            }
            seg[n].p = 0;
        }
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p += k;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s, e, k, 2*n, ns, mid);
        add(s, e, k, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n].p = max(seg[2*n].p, seg[2*n+1].p);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return -INF;
        if(s<=ns&&ne<=e) return seg[n].ma;
        int mid = ns + ne >> 1;
        return max(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
    int find_left(int L, int N) {
        if(sum(0, N, 1, 0, MAX/2) < L) return N;
        int s = 0, e = N;
        while(s+1<e) {
            int mid = (s+e)/2;
            if(sum(0, mid, 1, 0, MAX/2) < L) s = mid;
            else e = mid;
        }
        return s;
    }
    int find_right(int R, int N) {
        if(sum(0, N, 1, 0, MAX/2) < R) return -1;
        int s = 0, e = N;
        while(s+1<e) {
            int mid = (s+e)/2;
            if(sum(mid, N, 1, 0, MAX/2) < R) e = mid;
            else s = mid;
        }
        return s;
    }
};
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, Q;
    cin >> N >> Q;
    int i, j;
    for(i=0;i<Q;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(b==1) A[i] = {0, 4*c, -2*a};
        if(b==2) A[i] = {1, 2*a, 4*c};
    }
    reverse(A, A+Q);
    SegTree tx(N+3), ty(N+3);
    int MAX = tx.MAX;
    for(i=0;i<N;i++) {
        tx.seg[i+MAX/2].ma = 2*i+1;
        ty.seg[i+MAX/2].ma = -2*i-1;
    }
    tx.cons();
    ty.cons();
    //cout << "Start\n";
    for(j=0;j<Q;j++) {
        if(A[j][0]==0) {
            int pt = ty.find_right(A[j][2], N);
            tx.add(0, pt+1, -A[j][1], 1, 0, MAX/2);
        }
        else {
            int pt = tx.find_left(A[j][1], N);
            ty.add(pt, N, -A[j][2], 1, 0, MAX/2);
        }
    }
    for(i=0;i<N;i++) {
        int x = tx.sum(i, i+1, 1, 0, MAX/2);
        int y = ty.sum(i, i+1, 1, 0, MAX/2);
        cout << -(x+y)/4 << '\n';
    }
}

Compilation message (stderr)

2016_ho_t5.cpp: In member function 'void SegTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
2016_ho_t5.cpp:43:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
2016_ho_t5.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
2016_ho_t5.cpp:52:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 66 / 66