Submission #338888

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338888	2020-12-24T06:55:08 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	323 ms	62700 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 = 1e8+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(!cont[x]) return 0;
	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

#	Verdict	Execution time	Memory	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	21 ms	1260 KB	Output is correct
5	Correct	26 ms	1260 KB	Output is correct
6	Correct	26 ms	1260 KB	Output is correct
7	Correct	28 ms	1260 KB	Output is correct
8	Correct	145 ms	3820 KB	Output is correct
9	Correct	312 ms	4608 KB	Output is correct
10	Correct	307 ms	6016 KB	Output is correct
11	Correct	319 ms	7276 KB	Output is correct
12	Correct	323 ms	8044 KB	Output is correct
13	Incorrect	203 ms	62700 KB	Output isn't correct
14	Halted	0 ms	0 KB	-