Submission #338897

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338897	2020-12-24T07:15:19 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	6252 KB

apple

/** made by amunduzbaev **/
#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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];

inline 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;
}

inline 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;
}

inline 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;
}

inline 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;
}

Compilation message

apple.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
apple.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

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	64 ms	1004 KB	Output is correct
5	Correct	33 ms	1004 KB	Output is correct
6	Correct	34 ms	1004 KB	Output is correct
7	Correct	42 ms	1004 KB	Output is correct
8	Correct	225 ms	2796 KB	Output is correct
9	Correct	395 ms	3564 KB	Output is correct
10	Correct	397 ms	4716 KB	Output is correct
11	Correct	454 ms	5612 KB	Output is correct
12	Correct	414 ms	6252 KB	Output is correct
13	Execution timed out	2071 ms	764 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-