oj.uz

답안 #500930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500930 2022-01-01T17:13:22 Z mars4 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
 381 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);
	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 316 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 16 ms 8620 KB Output is correct
5 Correct 20 ms 10436 KB Output is correct
6 Correct 22 ms 10096 KB Output is correct
7 Correct 19 ms 10504 KB Output is correct
8 Correct 156 ms 77764 KB Output is correct
9 Correct 326 ms 132740 KB Output is correct
10 Correct 337 ms 148676 KB Output is correct
11 Correct 357 ms 161200 KB Output is correct
12 Correct 369 ms 166596 KB Output is correct
13 Correct 331 ms 207164 KB Output is correct
14 Correct 330 ms 209220 KB Output is correct
15 Runtime error 381 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -