fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=2e5+5;
  5. int sz;
  6. pair<int, int> tree[4*N];
  7.  
  8. void init(int n)
  9. {
  10. 	sz=1;
  11. 	while(sz<n)
  12. 		sz*=2;
  13. }
  14.  
  15. int query(int i, int node, int lx, int rx)
  16. {
  17. 	if(rx-lx==1)
  18. 		return tree[node].first;
  19. 	int mid=(lx+rx)/2;
  20. 	if(tree[2*node+1].second<tree[node].second)
  21. 		tree[2*node+1]=tree[node];
  22. 	if(tree[2*node+2].second<tree[node].second)
  23. 		tree[2*node+2]=tree[node];
  24. 	tree[node]={0, 0};
  25. 	if(i<mid)
  26. 		return query(i, 2*node+1, lx, mid);
  27. 	return query(i, 2*node+2, mid, rx);
  28. }
  29.  
  30. void update(int l, int r, int v, int node, int lx, int rx, int no)
  31. {
  32. 	if(lx>=r || rx<=l)
  33. 		return;
  34. 	if(lx>=l && rx<=r)
  35. 	{
  36. 		tree[node]={v, no};
  37. 		return;
  38. 	}
  39. 	int mid=(lx+rx)/2;
  40. 	update(l, r, v, 2*node+1, lx, mid, no);
  41. 	update(l, r, v, 2*node+2, mid, rx, no);
  42. }
  43.  
  44. void solve()
  45. {
  46. 	int n, m;
  47. 	cin>>n>>m;
  48.  
  49. 	for(int i=0;i<4*N;i++)
  50. 		tree[i]={0, 0};
  51.  
  52. 	init(n);
  53.  
  54. 	int up=0;
  55.  
  56. 	while(m--)
  57. 	{
  58. 		int op;
  59. 		cin>>op;
  60. 		if(op==2)
  61. 		{
  62. 			int i;
  63. 			cin>>i;
  64. 			int ans=query(i, 0, 0, sz);
  65. 			cout<<ans<<endl;
  66. 		}
  67. 		else
  68. 		{
  69. 			int l, r, v;
  70. 			cin>>l>>r>>v;
  71. 			update(l, r, v, 0, 0, sz, ++up);
  72. 		}
  73. 	}
  74.  
  75.  
  76. }
  77.  
  78. signed main() {
  79.  
  80.     	// int t;cin>>t;while(t--)
  81. 	    solve();
  82.  
  83.  
  84. return 0;
  85. }
Time limit exceeded #stdin #stdout 5s 9604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aRGGfI
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

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!