Submission #316599

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316599	2020-10-26T21:16:19 Z	AmineWeslati	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	336 ms	153464 KB

apple

//Never stop trying
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef string str;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 1e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

#define dbg(x) cerr << " - " << #x << " : " << x << endl;
#define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;

void IO() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

struct node{
	int sum=0,lazy=0,tl,tr,l=-1,r=-1;
};

node t[64*MX];
int cnt=1;

void push_down(int pos){
	int tl=t[pos].tl,tr=t[pos].tr,mid=(tl+tr)/2;

	if(t[pos].l==-1){
		t[pos].l=++cnt;
		t[pos].r=++cnt;
		t[t[pos].l].tl=tl , t[t[pos].l].tr=mid;
		t[t[pos].r].tl=mid+1 , t[t[pos].r].tr=tr;
	}
	if(t[pos].lazy){
		t[t[pos].l].lazy=t[t[pos].r].lazy=1;
		t[t[pos].l].sum=mid-tl+1; t[t[pos].r].sum=tr-mid;
		t[pos].lazy=0;
	}
}


void update(int l, int r, int pos=1){
	if(l>r) return;
	int tl=t[pos].tl,tr=t[pos].tr;

	if(l==tl && r==tr){
		t[pos].lazy=1;
		t[pos].sum=tr-tl+1;
		return;
	}

	push_down(pos);

	int mid=(tl+tr)/2;
	update(l,min(mid,r),t[pos].l);
	update(max(mid+1,l),r,t[pos].r);

	t[pos].sum=t[t[pos].l].sum+t[t[pos].r].sum;
}

int query(int l, int r, int pos=1){
	if(l>r) return 0;
	int tl=t[pos].tl,tr=t[pos].tr;

	if(l==tl && r==tr) return t[pos].sum;

	push_down(pos);
	int mid=(tl+tr)/2;
	return query(l,min(mid,r),t[pos].l) +
		query(max(mid+1,l),r,t[pos].r);
}

int main() {
	boost; 

	t[1].tl=1,t[1].tr=1e9;

	int M; cin>>M;
	int c=0;
	while(M--){
		int t,l,r; cin>>t>>l>>r;
		if(t==1){
			c=query(l+c,r+c);
			cout << c << endl;
		} else update(l+c,r+c);
	}

	return 0;
}

/* Careful!!!
	.Array bounds
	.Infinite loops
	.Uninitialized variables / empty containers
	.Order of input

   Some insights:
	.Binary search
	.Graph representation
	.Write brute force code
	.Change your approach
*/

Compilation message

apple.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
apple.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
apple.cpp: In function 'void IO()':
apple.cpp:49:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  freopen("input.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  freopen("output.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	88 ms	150648 KB	Output is correct
2	Correct	92 ms	150648 KB	Output is correct
3	Correct	87 ms	150648 KB	Output is correct
4	Correct	97 ms	150776 KB	Output is correct
5	Correct	99 ms	150904 KB	Output is correct
6	Correct	99 ms	150780 KB	Output is correct
7	Correct	101 ms	150904 KB	Output is correct
8	Correct	182 ms	151692 KB	Output is correct
9	Correct	282 ms	152800 KB	Output is correct
10	Correct	292 ms	152824 KB	Output is correct
11	Correct	290 ms	152952 KB	Output is correct
12	Correct	294 ms	152856 KB	Output is correct
13	Correct	261 ms	153208 KB	Output is correct
14	Correct	264 ms	153192 KB	Output is correct
15	Correct	328 ms	153300 KB	Output is correct
16	Correct	330 ms	153336 KB	Output is correct
17	Correct	269 ms	153208 KB	Output is correct
18	Correct	270 ms	153208 KB	Output is correct
19	Correct	336 ms	153428 KB	Output is correct
20	Correct	325 ms	153464 KB	Output is correct