Submission #500959

# Submission time Handle Problem Language Result Execution time Memory
500959 2022-01-01T18:15:06 Z mars4 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
515 ms 262144 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int
#define ld              long double
#define nl              cout<<"\n"
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
	#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
	#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

class DynamicSegtree
{
	ll N;

	struct Node
	{
		Node *left;
		Node *right;
		ll val;
		ll lazy;

		Node(): left(NULL), right(NULL), val(0), lazy(-1) {}

		void extend()
		{
			if(left==NULL)
			{
				left=new Node();
				right=new Node();
			}
		}
	};

	void _push(Node *cur,ll st,ll ed,ll val)
	{
		if(st!=ed)
		{
			cur->extend();
			cur->left->lazy=val;
			cur->right->lazy=val;
		}
	}

	ll combine(ll a,ll b)
	{
		return a+b;
	}

	void _update(Node *cur,ll st,ll ed,ll l,ll r,ll val)
	{
		if(cur->lazy!=-1)
		{
			cur->val=cur->lazy*(ed-st+1);
			_push(cur,st,ed,cur->lazy);
			cur->lazy=-1;
		}
		if(st>ed or st>r or ed<l)
		{
			return;
		}
		if(st>=l and ed<=r)
		{
			cur->val=val*(ed-st+1);
			_push(cur,st,ed,val);
			return;
		}
		ll mid=(st+ed)>>1;
		cur->extend();
		_update(cur->left,st,mid,l,r,val);
		_update(cur->right,mid+1,ed,l,r,val);
		cur->val=combine(cur->left->val,cur->right->val);
	}

	ll _query(Node *cur,ll st,ll ed,ll l,ll r)
	{
		if(cur->lazy!=-1)
		{
			cur->val=cur->lazy*(ed-st+1);
			_push(cur,st,ed,cur->lazy);
			cur->lazy=-1;
		}
		if(st>ed or st>r or ed<l)
		{
			return 0;
		}
		if(st>=l and ed<=r)
		{
			return cur->val;
		}
		ll mid=(st+ed)>>1;
		cur->extend();
		return combine(_query(cur->left,st,mid,l,r),_query(cur->right,mid+1,ed,l,r));
	}

	public:
	Node *root;

	void init(ll n)
	{
		root=new Node();
		N=n;
	}

	void update(ll l,ll r,ll val)
	{
		_update(root,0,N-1,l,r,val);
	}

	ll query(ll l,ll r)
	{
		return _query(root,0,N-1,l,r);
	}
};

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	cin>>n;
	ll last=0;
	DynamicSegtree ds;
	ds.init(mod);
	forn(i,0,n)
	{
		cin>>d>>l>>r;
		if(d==1)
		{
			last=ds.query(l+last,r+last);
			cout<<last<<"\n";
		}
		else
		{
			ds.update(l+last,r+last,1);
		}
	}
	cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:151:5: warning: unused variable 'z' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
apple.cpp:151:9: warning: unused variable 'm' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |         ^
apple.cpp:151:11: warning: unused variable 't' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
apple.cpp:151:13: warning: unused variable 'k' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
apple.cpp:151:15: warning: unused variable 'i' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
apple.cpp:151:17: warning: unused variable 'j' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                 ^
apple.cpp:151:23: warning: unused variable 'h' [-Wunused-variable]
  151 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 14 ms 5712 KB Output is correct
5 Correct 18 ms 6988 KB Output is correct
6 Correct 18 ms 6720 KB Output is correct
7 Correct 18 ms 6988 KB Output is correct
8 Correct 139 ms 51432 KB Output is correct
9 Correct 285 ms 87516 KB Output is correct
10 Correct 313 ms 98144 KB Output is correct
11 Correct 313 ms 106564 KB Output is correct
12 Correct 319 ms 110064 KB Output is correct
13 Correct 284 ms 136936 KB Output is correct
14 Correct 292 ms 138340 KB Output is correct
15 Correct 481 ms 254288 KB Output is correct
16 Correct 490 ms 256580 KB Output is correct
17 Correct 350 ms 145444 KB Output is correct
18 Correct 306 ms 145456 KB Output is correct
19 Correct 515 ms 262144 KB Output is correct
20 Correct 498 ms 262144 KB Output is correct