fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define si(x)	scanf("%d",&x)
  8. #define sl(x)	scanf("%lld",&x)
  9. #define ss(s)	scanf("%s",s)
  10. #define pi(x)	printf("%d\n",x)
  11. #define pl(x)	printf("%lld\n",x)
  12. #define ps(s)	printf("%s\n",s)
  13. #define pb push_back
  14. #define mp make_pair
  15. #define F first
  16. #define S second
  17. #define all(x) x.begin(), x.end()
  18. #define clr(x) memset(x, 0, sizeof(x))
  19. #define sortall(x) sort(all(x))
  20. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  21. #define PI 3.1415926535897932384626
  22. typedef pair<int, int>	pii;
  23. typedef pair<ll, ll>	pl;
  24. typedef vector<int>		vi;
  25. typedef vector<ll>		vl;
  26. typedef vector<pii>		vpii;
  27. typedef vector<pl>		vpl;
  28. typedef vector<vi>		vvi;
  29. typedef vector<vl>		vvl;
  30. int mpow(int base, int exp); 
  31. void ipgraph(int m);
  32. void dfs(int u, int par);
  33. const int mod = 1000000007;
  34. const int N = 3e5, M = N;
  35. //=======================
  36.  
  37. vi g[N];
  38. int a[N], e[N];
  39. string s;
  40. ll root ;
  41. #define L 0
  42. #define R 1
  43. struct node{
  44. 	ll val;
  45. 	int lev;
  46. 	int dir;
  47. 	ll dif;
  48. 	void out(){
  49. 		cout << val <<" " << lev << " " <<dir << " " << dif << endl;
  50. 	}
  51. 	void par(){
  52. 		if(val==root)return; //invalid move
  53. 		if(dir==R)
  54. 			val-=dif;
  55. 		else val+=dif;
  56. 		copy(val);
  57. 	}
  58.  
  59. 	void left(){
  60. 		if(dif==1)return; //invalid move
  61. 		dif/=2;
  62. 		val-=dif;
  63. 		copy(val);
  64. 	}
  65. 	void right(){
  66. 		if(dif==1)return; //invalid move
  67. 		dif/=2;
  68. 		val+=dif;
  69. 		//found new val, update current node
  70. 		copy(val);
  71. 	}
  72. 	void copy(ll x){
  73. 		node to = go(x);
  74. 		val = to.val;
  75. 		lev = to.lev;
  76. 		dif = to.dif;
  77. 		dir = to.dir;
  78. 	}
  79. 	//takes a number x, and returns the particular
  80. 	//details of x = {value, level, left/right, difference with parent}
  81. 	node go(ll x){
  82. 		ll dif = root/2;
  83. 		ll cur = root;
  84. 		int l = 0;
  85. 		int dir = -1;
  86. 		while(cur != x){
  87. 			l++;
  88. 			if(cur<x){
  89. 				cur+=dif;
  90. 				dir=R;
  91. 			}
  92. 			else cur-=dif, dir=L;
  93. 			dif /= 2;
  94. 		}
  95. 		node ans = {x,l,dir,max(1LL,dif*2)};
  96. 		return ans;
  97. 	}
  98. };
  99.  
  100. int main()
  101. {
  102. 	ios_base::sync_with_stdio(false);
  103. 	cin.tie(NULL);
  104. 	ll i,n,k,j,q,u;
  105. 	cin >> n >> q;
  106. 	root = (n+1)/2;
  107. 	while(q--){
  108. 		cin >> u;
  109. 		cin >> s;
  110. 		n = s.size();
  111. 		node cur = cur.go(u);
  112. 		fo(i, n){
  113. 			if(s[i]=='U') cur.par();
  114. 			else if(s[i]=='L') cur.left();
  115. 			else if(s[i]=='R') cur.right();
  116. 		}
  117. 		cout << cur.val << endl;
  118. 	}
  119. 	return 0;
  120. } 
  121.  
Success #stdin #stdout 0s 24600KB
comments (?)
stdin
copy 
15 2
4
UURL
8
LRLLLLLLLL
stdout
copy 
10
5
https://ideone.com/iTDPGK
my template :)
language:
C++14 (gcc 8.3)
created:
7 years 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!