Submission #338864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338864	2020-12-24T05:33:43 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	639 ms	4716 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 = 1e7+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;

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];
}

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;
		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;
}

int find(int l, int r, int lx, int rx, int x){
	push(x, lx, rx);
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r && ful[x]) return ful[x] * (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;
	s = 2;
	while(s < N) s*=2;
	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, s, 1);
			cout<<c<<endl;
		}else{
			int l, r;
			cin>>l>>r;
			update(c + l, c + r, 1, s, 1);
		}
	}
	return;
}

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	69 ms	620 KB	Output is correct
5	Correct	28 ms	620 KB	Output is correct
6	Correct	38 ms	640 KB	Output is correct
7	Correct	50 ms	620 KB	Output is correct
8	Correct	208 ms	1516 KB	Output is correct
9	Correct	352 ms	2156 KB	Output is correct
10	Correct	338 ms	2540 KB	Output is correct
11	Correct	398 ms	3052 KB	Output is correct
12	Correct	351 ms	3308 KB	Output is correct
13	Incorrect	639 ms	4716 KB	Output isn't correct
14	Halted	0 ms	0 KB	-