Submission #338855

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338855	2020-12-24T05:09:58 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	574 ms	140012 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;

vii tree;
bitset<N*4> ff, val;

void push(int x, int lx, int rx){
	if(lx == rx || !ff[x])return;
	int len = (rx - lx+1)/2;
	val[(x<<1)+1] = val[x];
	val[(x<<1)] = val[x];
	tree[x<<1] = val[x<<1] * len;
	tree[(x<<1)+1] = val[(x<<1)+1] * len;
	ff[x<<1] = ff[(x<<1)+1] = ff[x];
	ff[x] = 0;
	val[x] = 0;
	tree[x] = tree[x<<1] + tree[(x<<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){
		val[x] = 1;
		ff[x] = 1;
		tree[x] = (rx - lx + 1);
		return;
	}
	int m =(lx + rx)>>1;
	update(l, r, lx, m, x*2);
	update(l, r, m+1, rx, x*2+1);
	tree[x] = tree[x*2] + tree[x*2+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) return tree[x];

	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;
	tree.assign(s*2, 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, s, 1);
			cout<<c<<endl;
		}else{
			int l, r;
			cin>>l>>r;
			update(c + l, c + r, 1, s, 1);
		}//cout<<tree[1]<<endl;
	}
	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	77 ms	131692 KB	Output is correct
2	Correct	76 ms	131692 KB	Output is correct
3	Correct	84 ms	131692 KB	Output is correct
4	Correct	102 ms	132204 KB	Output is correct
5	Correct	108 ms	132460 KB	Output is correct
6	Correct	108 ms	132332 KB	Output is correct
7	Correct	107 ms	132332 KB	Output is correct
8	Correct	291 ms	133868 KB	Output is correct
9	Correct	534 ms	134636 KB	Output is correct
10	Correct	571 ms	135660 KB	Output is correct
11	Correct	574 ms	136556 KB	Output is correct
12	Correct	571 ms	137196 KB	Output is correct
13	Incorrect	239 ms	140012 KB	Output isn't correct
14	Halted	0 ms	0 KB	-