oj.uz

답안 #500938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500938 2022-01-01T17:30:35 Z mars4 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 402 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(mod*2);
	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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 16 ms 8548 KB Output is correct
5 Correct 30 ms 10360 KB Output is correct
6 Correct 31 ms 9944 KB Output is correct
7 Correct 21 ms 10284 KB Output is correct
8 Correct 178 ms 76844 KB Output is correct
9 Correct 357 ms 130872 KB Output is correct
10 Correct 366 ms 146896 KB Output is correct
11 Correct 367 ms 159408 KB Output is correct
12 Correct 402 ms 164756 KB Output is correct
13 Correct 342 ms 205124 KB Output is correct
14 Correct 360 ms 207168 KB Output is correct
15 Runtime error 390 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -