Submission #338865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338865	2020-12-24T05:34:52 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	4076 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;

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;
	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	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	72 ms	748 KB	Output is correct
5	Correct	29 ms	748 KB	Output is correct
6	Correct	30 ms	748 KB	Output is correct
7	Correct	42 ms	748 KB	Output is correct
8	Correct	215 ms	2004 KB	Output is correct
9	Correct	368 ms	2432 KB	Output is correct
10	Correct	348 ms	3228 KB	Output is correct
11	Correct	410 ms	3948 KB	Output is correct
12	Correct	334 ms	4076 KB	Output is correct
13	Execution timed out	2075 ms	816 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-