Submission #154727

#	Time	Username	Problem	Language	Result	Execution time	Memory
154727		Pro_ktmr	Bridges (APIO19_bridges)	C++14	16 / 100	1690 ms	5632 KiB

bridges

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair

//RMQ RUQ
struct SegmentTree{
private:
    int N;
    vector<long long> node, lazy;
    vector<bool> lazyFlg;
public:
    void init(int n){
        N = 1;
        while(N < n) N *= 2;
        node.clear();
        lazy.clear();
        lazyFlg.clear();
        for(int i=0; i<N*2-1; i++){
            node.push_back(LLONG_MAX);
            lazy.push_back(0);
            lazyFlg.push_back(false);
        }
    }
    void eval(int k, int l, int r){
        if(lazyFlg[k] == false) return;
        node[k] = lazy[k];
        lazyFlg[k] = false;
        if(r-l > 1){
            lazy[2*k+1] = lazy[k];
            lazyFlg[2*k+1] = true;
            lazy[2*k+2] = lazy[k];
            lazyFlg[2*k+2] = true;
        }
    }
    void update(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            lazyFlg[k] = true;
            eval(k, l, r);
        }
        else{
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }
    long long query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r <= a || b <= l) return LLONG_MAX;
        if(a <= l && r <= b) return node[k];
        else return min(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
    }
};

int N,M,Q;
SegmentTree st;

int binary_searchL(int p, int w){
	int ok = p-1;
	int ng = M;
	while(ng - ok > 1){
		int m = (ok+ng)/2;
		if(st.query(p, m+1) >= w) ok = m;
		else ng = m;
	}
	return ok+1 - p;
}

int binary_searchR(int p, int w){
	int ok = p;
	int ng = -1;
	while(ok - ng > 1){
		int m = (ok+ng)/2;
		if(st.query(m, p) >= w) ok = m;
		else ng = m;
	}
	return p - ok;
}

int main(){
	cin >> N >> M;
	st.init(M);
	for(int i=0; i<M; i++){
		int a, b, c;
		cin >> a >> b >> c;
		st.update(i, i+1, c);
	}
	cin >> Q;
	for(int i=0; i<Q; i++){
		int t, a, b;
		cin >> t >> a >> b;
		if(t == 1){
			st.update(a-1, a, b);
		}
		else{
			int p = a-1;
			int w = b;
			cout << binary_searchL(p, w)+binary_searchR(p, w)+1 << endl;
		}
	}
	
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27