Submission #426648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426648	2021-06-14T08:35:42 Z	jeqcho	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	52 ms	21572 KB

apple

#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#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)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int const N=1e6+3;

template <class T>
struct segmentTree
{
	int arr_sz;
	vector<T> seg;
	vector<T> lazy;
	
	T comb(T a,T b){return a+b;}
	void pull(int x){seg[x]=comb(seg[2*x+1],seg[2*x+2]);}
	void push(int x,int lx,int rx)
	{
		if(!lazy[x])return;
		seg[x]=(rx-lx);
		if(rx-lx!=1)
		{
			lazy[2*x+1]=1;
			lazy[2*x+2]=1;
		}
		lazy[x]=0;
	}
	void init(int n,vector<T>&v)
	{
		int p = ceil(log2((ld)n));
		arr_sz = 1<<p;
		int tree_sz=arr_sz<<1;
		seg.rsz(tree_sz);
		lazy.rsz(tree_sz);
	}
	T query(int x,int lq,int rq,int lx,int rx)
	{
		push(x,lx,rx);
		if(lq>=rx || rq<=lx)return 0;
		if(lq<=lx && rq>=rx)return seg[x];
		int md=(lx+rx)/2;
		T lef=query(2*x+1,lq,rq,lx,md);
		T rig=query(2*x+2,lq,rq,md,rx);
		return comb(lef,rig);
	}
	T query(int lq,int rq)
	{
		return query(0,lq,rq,0,arr_sz);
	}
	void update(int x,int lq,int rq,int lx,int rx,T v)
	{
		push(x,lx,rx);
		if(lq>=rx || rq<=lx)return;
		if(lq<=lx && rq>=rx)
		{
			lazy[x]=v;
			push(x,lx,rx);
			return;
		}
		int md=(lx+rx)/2;
		update(2*x+1,lq,rq,lx,md,v);
		update(2*x+2,lq,rq,md,rx,v);
		pull(x);
	}
	void update(int lq,int rq,T v)
	{
		update(0,lq,rq,0,arr_sz,v);
	}	
};

segmentTree<int>seg;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int m;
	cin>>m;
	int c=0;
	vi a(N);
	seg.init(N,a);
	while(m--)
	{
		int d,x,y;
		cin>>d>>x>>y;
		if(d==1)
		{
			c=seg.query(c+x,c+y+1);
			cout<<c<<'\n';
		}
		else
		{
			seg.update(c+x,c+y+1,1);
		}
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	20556 KB	Output is correct
2	Correct	12 ms	20556 KB	Output is correct
3	Correct	14 ms	20636 KB	Output is correct
4	Correct	25 ms	20704 KB	Output is correct
5	Correct	28 ms	20820 KB	Output is correct
6	Correct	28 ms	20832 KB	Output is correct
7	Correct	29 ms	20812 KB	Output is correct
8	Incorrect	52 ms	21572 KB	Output isn't correct
9	Halted	0 ms	0 KB	-