답안 #338895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338895	2020-12-24T07:11:46 Z	amunduzbaev	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	2000 ms	6124 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, tmp = 1073741824;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, ans, cur;

bitset<tmp> 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

#	결과	실행 시간	메모리	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	88 ms	1128 KB	Output is correct
5	Correct	38 ms	1004 KB	Output is correct
6	Correct	38 ms	1004 KB	Output is correct
7	Correct	48 ms	1100 KB	Output is correct
8	Correct	252 ms	2860 KB	Output is correct
9	Correct	440 ms	3564 KB	Output is correct
10	Correct	450 ms	4588 KB	Output is correct
11	Correct	514 ms	5868 KB	Output is correct
12	Correct	466 ms	6124 KB	Output is correct
13	Execution timed out	2073 ms	848 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-