oj.uz

답안 #266494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266494 2020-08-15T10:22:55 Z define 다리 (APIO19_bridges) C++17
16 / 100
 1409 ms 5496 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
auto f=[](int a,int b){return min(a,b);};
auto g=[](int a,int b,int sz){return b;};
auto h=[](int a,int b){return b;};
int N,M,Q;
signed main(){
	cin>>N>>M;
	Segtree<int,int,decltype(f),decltype(g),decltype(h)>segtree(N,f,g,h,inf,inf);
	rep(i,M){
		int a;cin>>a>>a>>a;
		segtree.set(i,a);
	}
	segtree.init();
	int Q;cin>>Q;
	while(Q--){
		int type;cin>>type;
		if(type==1){
			int a,b;cin>>a>>b;a--;
			segtree.update(a,a+1,b);
		}else {
			int a,b;cin>>a>>b;a--;
			int ok=a,ng=-1;
			while(ok-ng>1){
				int mid=(ok+ng)/2;
				if(segtree.query(mid,a)>=b)ok=mid;
				else ng=mid;
			}
			int ok2=a,ng2=N;
			while(ng2-ok2>1){
				int mid=(ok2+ng2)/2;
				if(segtree.query(a,mid)>=b)ok2=mid;
				else ng2=mid;
			}
			cout<<ok2-ok+1<<endl;
		}
	}
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 850 ms 2552 KB Output is correct
2 Correct 851 ms 2552 KB Output is correct
3 Correct 845 ms 2680 KB Output is correct
4 Correct 853 ms 2936 KB Output is correct
5 Correct 863 ms 2552 KB Output is correct
6 Correct 972 ms 2808 KB Output is correct
7 Correct 980 ms 5368 KB Output is correct
8 Correct 932 ms 5276 KB Output is correct
9 Correct 359 ms 1912 KB Output is correct
10 Correct 806 ms 4472 KB Output is correct
11 Correct 809 ms 4216 KB Output is correct
12 Correct 1409 ms 5496 KB Output is correct
13 Correct 415 ms 5112 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 754 ms 1660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 131 ms 4600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 850 ms 2552 KB Output is correct
2 Correct 851 ms 2552 KB Output is correct
3 Correct 845 ms 2680 KB Output is correct
4 Correct 853 ms 2936 KB Output is correct
5 Correct 863 ms 2552 KB Output is correct
6 Correct 972 ms 2808 KB Output is correct
7 Correct 980 ms 5368 KB Output is correct
8 Correct 932 ms 5276 KB Output is correct
9 Correct 359 ms 1912 KB Output is correct
10 Correct 806 ms 4472 KB Output is correct
11 Correct 809 ms 4216 KB Output is correct
12 Correct 1409 ms 5496 KB Output is correct
13 Correct 415 ms 5112 KB Output is correct
14 Incorrect 754 ms 1660 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -