Submission #338896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338896	2020-12-24T07:14:59 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	6124 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	63 ms	1004 KB	Output is correct
5	Correct	33 ms	1004 KB	Output is correct
6	Correct	35 ms	1004 KB	Output is correct
7	Correct	45 ms	1132 KB	Output is correct
8	Correct	237 ms	2924 KB	Output is correct
9	Correct	404 ms	3692 KB	Output is correct
10	Correct	416 ms	4584 KB	Output is correct
11	Correct	483 ms	5740 KB	Output is correct
12	Correct	446 ms	6124 KB	Output is correct
13	Execution timed out	2078 ms	620 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-