Submission #338892

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

bitset<N*4> ful[2], cont[2];

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

void update(int l, int r, int lx, int rx, int x){
	push(x, lx, rx);
	if(lx >= l && rx <= r && ful[cur][x]) return;
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		ful[cur][x] = 1;
		cont[cur][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[cur][x*2] && ful[cur][x*2+1]) ful[cur][x] = 1;
	if(cont[cur][x*2] || cont[cur][x*2+1]) cont[cur][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[cur][x]) return (rx - lx+1);
	if(lx == rx && !ful[cur][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;
			l+=c, r+=c;
			if(l <= N && r <= N){
				cur = 0;
				c = find(l, r, 1, N, 1);
				cout<<c<<endl;
			} else if(l > n && r > N){
				cur = 1;
				c = find(l, r, 1, N, 1);
				cout<<c<<endl;
			} else{
				cur = 0, c = find(l, N, 1, N, 1);
				cur = 1, c += find(1, r, 1, N, 1);
				cout<<c<<endl;
			}
		}else{
			int l, r;
			cin>>l>>r;
			l+=c, r+=c;
			if(l <= N && r <= N){
				cur = 0;
				update(l, r, 1, N, 1);
			} else if(l > n && r > N){
				cur = 1;
				update(l, r, 1, N, 1);
			} else{
				cur = 0, update(l, N, 1, N, 1);
				cur = 1, update(1, 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	640 KB	Output is correct
2	Correct	1 ms	500 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	71 ms	1132 KB	Output is correct
5	Correct	33 ms	1132 KB	Output is correct
6	Correct	34 ms	1004 KB	Output is correct
7	Correct	44 ms	1132 KB	Output is correct
8	Correct	235 ms	2924 KB	Output is correct
9	Correct	396 ms	3564 KB	Output is correct
10	Correct	412 ms	4716 KB	Output is correct
11	Correct	452 ms	5612 KB	Output is correct
12	Correct	391 ms	6380 KB	Output is correct
13	Execution timed out	2090 ms	620 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-