oj.uz

답안 #500952

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500952 2022-01-01T18:05:35 Z mars4 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 405 ms 262148 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              int64_t
#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(inf);
	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;
      |                       ^

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 18 ms 8604 KB Output is correct
5 Correct 21 ms 10364 KB Output is correct
6 Correct 20 ms 10004 KB Output is correct
7 Correct 20 ms 10352 KB Output is correct
8 Correct 173 ms 76848 KB Output is correct
9 Correct 374 ms 130628 KB Output is correct
10 Correct 346 ms 146604 KB Output is correct
11 Correct 405 ms 159092 KB Output is correct
12 Correct 379 ms 164364 KB Output is correct
13 Correct 362 ms 204900 KB Output is correct
14 Correct 381 ms 206932 KB Output is correct
15 Runtime error 386 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -