oj.uz

Submission #154727

# Submission time Handle Problem Language Result Execution time Memory
154727 2019-09-24T09:06:44 Z Pro_ktmr Bridges (APIO19_bridges) C++14
16 / 100
 1690 ms 5632 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 2836 KB Output is correct
2 Correct 876 ms 2852 KB Output is correct
3 Correct 873 ms 2852 KB Output is correct
4 Correct 874 ms 2784 KB Output is correct
5 Correct 863 ms 2852 KB Output is correct
6 Correct 922 ms 4136 KB Output is correct
7 Correct 920 ms 5472 KB Output is correct
8 Correct 917 ms 5632 KB Output is correct
9 Correct 389 ms 1912 KB Output is correct
10 Correct 846 ms 4588 KB Output is correct
11 Correct 835 ms 4480 KB Output is correct
12 Correct 1409 ms 5616 KB Output is correct
13 Correct 421 ms 5480 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 782 ms 1800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1690 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 2836 KB Output is correct
2 Correct 876 ms 2852 KB Output is correct
3 Correct 873 ms 2852 KB Output is correct
4 Correct 874 ms 2784 KB Output is correct
5 Correct 863 ms 2852 KB Output is correct
6 Correct 922 ms 4136 KB Output is correct
7 Correct 920 ms 5472 KB Output is correct
8 Correct 917 ms 5632 KB Output is correct
9 Correct 389 ms 1912 KB Output is correct
10 Correct 846 ms 4588 KB Output is correct
11 Correct 835 ms 4480 KB Output is correct
12 Correct 1409 ms 5616 KB Output is correct
13 Correct 421 ms 5480 KB Output is correct
14 Incorrect 782 ms 1800 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -