fork download
copy 
  1. /* Creation Date - 30-01-2023 */  
  2. /* Creation Time - 22:11:00.00 */  
  3. #define ill 
  4. /*
  5. Written By : mafailure
  6. In the name of God 
  7. O Allah, May you grant peace and honor on Muhammad and his family.
  8. Allahumm-a-Sall-iAla Muhammad-in Wa Al-i Muhammad
  9. */
  10.  
  11. #ifdef LOCAL 
  12. #define AATIF_DEBUG
  13. #endif 
  14. /*Add -DLOCAL in 
  15. compiler command 
  16. to trigger it*/
  17.  
  18. #include<bits/stdc++.h>
  19. #include <ext/pb_ds/assoc_container.hpp> // Common file 
  20. #include <ext/pb_ds/tree_policy.hpp> 
  21. #include <functional> // for less
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25.  
  26. #define endl "\n"
  27. /*------------------------int to long long -----------------*/
  28. #ifdef ill
  29. #define int long long 
  30. #endif
  31. /*---------------------------DEBUG HELPER--------------------------------------*/
  32. template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
  33. template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
  34. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  35. template<typename T,typename K> ostream& operator<<(ostream & os,const map<T,K> & mapp){ os<<"{"; string sep=""; for(const auto& x:mapp)os<<sep<<x,sep=", "; return os<<'}'; }
  36. template <typename T> ostream & operator<<(ostream & os,const set<T> & sett){os<<'{'; string sep=""; for(const auto & x:sett)os<<sep<<x,sep=", "; return os<<'}';}
  37.  
  38. void dbg_out() { cerr << endl; }
  39. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  40.  
  41. #ifdef AATIF_DEBUG
  42. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  43. #else
  44. #define dbg(...)
  45. #endif
  46.  
  47. //#define int long long 
  48. // int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1};
  49. // int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};
  50. #ifndef mod_2 
  51. long long mod = 1e9 + 7;
  52. #else 
  53. long long mod =998244353; 
  54. #endif 
  55. const double eps=1e-9;
  56. typedef vector<int> vi;
  57. typedef vector<vi> vvi;
  58. typedef vector<string> vs;
  59. typedef vector<bool> vb;
  60. typedef pair<int, int> ii;
  61. typedef vector< pair< int, int > > vii;
  62. typedef map<int, int> mii;
  63. typedef pair<int, ii> pip;
  64. typedef pair<ii, int> ppi;
  65. #define arrinp(arr,init,final,size,type) type* arr=new type[size];for(int i=init;i<final;i++)cin>>arr[i];
  66. #define cr2d(arr,n,m,t) t**arr=new t*[n];for(int i=0;i<n;i++)arr[i]=new t[m];
  67. #define w(t) int t;cin>>t; while(t--)
  68. #define takeInp(n) int n;cin>>n;
  69. #define fr(i,init,final) for(int i=init;i<final;i++)
  70. #define frr(i,init,final) for(int i=init;i>=final;i--)
  71. #define Fr(i,final) for(int i=0;i<final;i++)
  72. #define Frr(i,first) for(int i=first;i>=0;i--)
  73. #define fi first
  74. #define se second
  75. #define mp make_pair
  76. #define pb push_back
  77. #define all(c) (c).begin(),(c).end()
  78. #define rall(c) (c).rbegin(),(c).rend()
  79. #define debug(x) cerr<<">value ("<<#x<<") : "<<x<<endl;
  80. #define setb __builtin_popcount
  81. #define lsone(n) (n&(-n))
  82. #define rlsone(n) (n&(n-1))
  83. #define clr(a,b) memset(a,b,sizeof(a))
  84. #ifdef ill 
  85. const int inf =1e18; 
  86. #else 
  87. const int inf=1e9;
  88. #endif
  89. /*-----------------------------RANDOM NUMBER GENERATOR ---------------------*/
  90. #ifdef RNG 
  91. unsigned seed=chrono::high_resolution_clock::now().time_since_epoch().count();
  92. mt19937 rng(seed);
  93. #endif 
  94. /*------------------------------UNORDERED MAP HASH --------------------------------------------*/
  95. //To make unordered_map unhackable 
  96. // use it as unordered_map<int,int,custom_hash> mapp;
  97. struct custom_hash {
  98.     static uint64_t splitmix64(uint64_t x) {
  99.         /* http://x...content-available-to-author-only...i.it/splitmix64.c */
  100.         x += 0x9e3779b97f4a7c15;
  101.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  102.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  103.         return x ^ (x >> 31);
  104.     }
  105.  
  106.     size_t operator()(uint64_t x) const {
  107.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  108.         return splitmix64(x + FIXED_RANDOM);
  109.     }
  110. };
  111. /*---------------------------ORDERED SET--------------------------------------*/
  112. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set; 
  113. /*----------------------------------------------------------------------------*/
  114. vi init(string s)
  115. {
  116. 	istringstream sin(s);
  117. 	int n;
  118. 	vi arr;
  119. 	while(sin>>n)arr.push_back(n);
  120. 	return arr;
  121. }
  122. int power(int x, int y,int mod)
  123. { 
  124. 	if(y==0)return 1;
  125. 	int u=power(x,y/2,mod);
  126. 	u=(u*u)%mod;
  127. 	if(y%2)u=(x*u)%mod;
  128. 	return u;
  129.  
  130. }
  131. int gcd(int a,int b)
  132. {
  133. 	if(a<b)return gcd(b,a);
  134. 	return (b==0?a:(a%b?gcd(b,a%b):b));
  135. }
  136. int gcd_e(int a,int b,int &x,int &y)
  137. {
  138.  
  139. 	if(b==0){x=1; y=0; return a;}
  140. 	int x1,y1;
  141. 	int p=gcd_e(b,a%b,x1,y1);
  142. 	x=y1;
  143. 	y=x1-(a/b)*y1;
  144. 	return p;
  145. }
  146. /*-----------------to solve int to long long problem-----------------*/
  147. int Min (int a,int b){return min(a,b);}
  148. int Max(int a,int b){ return max(a,b);}
  149. inline int add(int a,int b,int mod=mod){return (a+b)%mod;} 
  150. inline int sub(int a,int b,int mod=mod){return (a-b+mod)%mod;}
  151. inline int mul(int a,int b,int mod=mod){return (a*b%mod);}
  152. //inline int divide(int a,int b,int mod=mod){return a*power(b,mod-2)%mod;}
  153. inline int high(int a,int b){return (a>>b)&1;}
  154. //786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121
  155. /*========================CODE*****CODE****CODE======================*/
  156.  
  157. template<const int X=2> 
  158. class StringHashing
  159. {
  160. 	using T=array<int,X> ; 
  161. 	public: 
  162. 	function<T(int,int)> get_sub; 
  163. 	function<bool(int,int,int,int)> match_two_sub; 
  164. 	vector<T> hash,pp,ipp; 
  165. 	T p,ip,mod; 
  166. 	StringHashing(int N)
  167. 	{
  168. 		/*TODO Base values of mod, p, ip needs to be updated if you are using different X*/
  169. 		mod={(int)1e9+7,(int)1e8+7}; 
  170. 		p={37,43}; 
  171. 		ip={power(p[0],mod[0]-2,mod[0]),power(p[1],mod[1]-2,mod[1])}; 
  172. 		T base_val; 
  173. 		base_val.fill(1); 
  174. 	    pp=vector<T>(N,base_val); 
  175. 	    ipp=vector<T>(N,base_val); 
  176. 		for(int i=1;i<N;i++)
  177. 		{
  178. 			for(int j=0;j<X;j++)
  179. 			{
  180. 				pp[i][j]=mul(pp[i-1][j],p[j],mod[j]); 
  181. 				ipp[i][j]=mul(ipp[i-1][j],ip[j],mod[j]); 
  182. 			}
  183. 		}
  184. 	}
  185.  
  186.  
  187. };
  188. #include<bits/stdc++.h>
  189. using namespace std; 
  190. template<class T=int> 
  191. struct FenwickTree:vector<T>
  192. {
  193. 	public: 
  194. 	//inline int lsone(int i){return (i&(-i));}
  195. 	template<typename... Args> 
  196. 	FenwickTree(Args... args):vector<T>(args...){;}
  197. 	void update(int ind,T val,function<T(const T, const T)> f)
  198. 	{
  199. 		vector<T> & ft= *this; 
  200. 		for(int i=ind;i<ft.size();i+=lsone(i))ft[i]=f(ft[i],val); 
  201. 	}
  202. 	T query(int ind, T ans, function<T(const T,const T)> f)
  203. 	{
  204. 		vector<T> & ft = *this; 
  205. 		for(int i=ind;i;i-=lsone(i))ans=f(ft[i],ans); 
  206. 		return ans; 
  207. 	}
  208. 	T query_max(int ind ,int ans)
  209. 	{
  210. 	 	return query(ind,ans,[](T a,T b)->T{return a>b?a:b;}); 
  211. 	}
  212. 	T query_min(int ind,int ans)
  213. 	{
  214. 		return query(ind, ans,[](T a,T b)->T{return a<b?a:b;}); 
  215. 	}
  216. 	T query_cnt(int ind,int ans,int mod)
  217. 	{
  218. 		return query(ind, ans, [&](T a, T b)->T{return add(a,b,mod);}); 
  219. 	}
  220. 	void update_max(int ind,int val)
  221. 	{
  222. 		update(ind,val,[](T a,T b){return a>b?a:b;}); 
  223. 	}
  224. 	void update_min(int ind,int val)
  225. 	{
  226. 		update(ind,val,[](T a,T b){return a<b?a:b;}); 
  227. 	}
  228. 	void update_cnt(int ind,int val,int mod)
  229. 	{
  230. 		update(ind,val,[&](T a,T b){return add(a,b,mod);}); 
  231. 	}
  232.  
  233.  
  234.  
  235. };
  236.  
  237. signed main()
  238. {
  239. 	IOS
  240. 	using T=array<int,2>; 
  241. 	int n,m; 
  242. 	cin>>n>>m; 
  243. 	int swapped=0;
  244. 	if(n>m)swapped=1,swap(n,m);
  245. 	vector<vector<FenwickTree<int>>> ft(n,vector<FenwickTree<int>>(2,FenwickTree<int>(m+1)));
  246. 	int q; 
  247. 	cin>>q; 
  248. 	vector<array<int,6>> store(q); 
  249. 	map<int,int> mapp;  
  250. 	for(int i=0;i<q;i++)
  251. 	{
  252. 		cin>>store[i][0]; 
  253. 		if(store[i][0]==1)fr(j,1,6)cin>>store[i][j]; 
  254. 		else fr(j,1,5)cin>>store[i][j];
  255. 		if(store[i][0]==1)mapp[store[i][5]]++; 
  256.  
  257. 	}
  258. 	int id=1; 
  259. 	for(auto & it:mapp)it.se=id++;
  260. 	StringHashing<2> helper(id+5);
  261. 	vector<T> hash(id+5); 
  262. 	fr(i,0,id+5)hash[i]=helper.pp[i]; 
  263. 	for(int i=0;i<q;i++)
  264. 	{
  265. 		if(store[i][0]==1)
  266. 		{
  267. 			int xa,ya,xb,yb; 
  268. 			xa=store[i][1],ya=store[i][2];
  269. 			xb=store[i][3],yb=store[i][4]; 
  270. 			if(swapped)swap(xa,ya),swap(xb,yb); 
  271. 			int c=mapp[store[i][5]]; 
  272. 			fr(x,xa-1,xb)
  273. 			{
  274. 				fr(j,0,2)
  275. 				ft[x][j].update_cnt(ya,hash[c][j],helper.mod[j]),
  276. 				ft[x][j].update_cnt(yb+1,sub(0,hash[c][j],helper.mod[j]),helper.mod[j]); 
  277. 			}
  278. 		}
  279. 		else 
  280. 		{
  281. 			int xa,ya,xb,yb; 
  282. 			xa=store[i][1],ya=store[i][2];
  283. 			xb=store[i][3],yb=store[i][4];
  284. 			if(swapped)swap(xa,ya),swap(xb,yb); 
  285. 			bool ok=1;
  286. 			fr(j,0,2)
  287. 			{
  288. 				if(ft[xa-1][j].query_cnt(ya,0,helper.mod[j])!=ft[xb-1][j].query_cnt(yb,0,helper.mod[j]))ok=0;	
  289. 			}
  290. 			cout<<(ok?"YES":"NO")<<endl; 
  291. 		}
  292. 	}
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301. }
  302.  
  303.  
  304.  
  305.  
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b6DWWc
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!