답안 #338889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338889	2020-12-24T06:56:19 Z	amunduzbaev	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	2000 ms	6124 KB

apple

/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 5e8+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, ans;

bitset<N*4> ful, cont;

void push(int x, int lx, int rx){
	if(lx == rx || !ful[x])return;
	ful[(x<<1)+1] = ful[x];
	ful[(x<<1)] = ful[x];
	cont[x<<1] = cont[(x<<1)+1] = 1;
}

void update(int l, int r, int lx, int rx, int x){
	push(x, lx, rx);
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		ful[x] = 1;
		cont[x] = 1;
		return;
	}
	int m =(lx + rx)>>1;
	update(l, r, lx, m, x*2);
	update(l, r, m+1, rx, x*2+1);
	if(ful[x*2] && ful[x*2+1]) ful[x] = 1;
	if(cont[x*2] || cont[x*2+1]) cont[x] = 1;
}

int find(int l, int r, int lx, int rx, int x){
	push(x, lx, rx);
	if(lx > r || rx < l) return 0; // || !cont[x]) return 0;
	if(lx >= l && rx <= r && ful[x]) return (rx - lx+1);
	if(lx == rx && !ful[x]) return 0;
	int m = (lx + rx)/2;
	int res = find(l, r, lx, m, x*2);
	res += find(l, r, m+1, rx, x*2+1);
	return res;
}

void solve(){
	fastios
	cin>>m;
	int c = 0;
	for(int i=0;i<m;i++){
		int t;
		cin>>t;
		if(t == 1){
			int l, r;
			cin>>l>>r;
			c = find(c + l,  c + r, 1, N, 1);
			cout<<c<<endl;
		}else{
			int l, r;
			cin>>l>>r;
			update(c + l, c + r, 1, N, 1);
		}
	}
	return;
}

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	71 ms	1004 KB	Output is correct
5	Correct	31 ms	1132 KB	Output is correct
6	Correct	32 ms	1004 KB	Output is correct
7	Correct	42 ms	1132 KB	Output is correct
8	Correct	242 ms	2796 KB	Output is correct
9	Correct	383 ms	3564 KB	Output is correct
10	Correct	384 ms	4716 KB	Output is correct
11	Correct	441 ms	5796 KB	Output is correct
12	Correct	376 ms	6124 KB	Output is correct
13	Execution timed out	2080 ms	876 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-