fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include<map>
  3. using namespace std;
  4.  
  5. // int temp[1000000];f
  6. map<int, int> nemE ;
  7.  
  8. bool updateBIT(int BITree[], int n, int index, int val)
  9. {
  10. 	bool upd = false;
  11.     index = index + 1;
  12.     while (index <= n)
  13.     {
  14.     	upd = true;
  15.         BITree[index] += val;
  16.         index += index & (-index);
  17.     }
  18.     return upd;
  19. }
  20.  
  21. int *constructBITree(int arr[], int n)
  22. {
  23.     int *BITree = new int[n+1];
  24.     for (int i=1; i<=n; i++)
  25.         BITree[i] = 0;
  26.  
  27.     for (int i=0; i<n; i++)
  28.         updateBIT(BITree, n, i, arr[i]);
  29.  
  30.     return BITree;
  31. }
  32.  
  33. int getSum(int BITree[], int index)
  34. {
  35.     int sum = 0; 
  36.     index = index + 1;
  37.     while (index>0)
  38.     {
  39.         sum += BITree[index];
  40.         index -= index & (-index);
  41.     }
  42.     return sum;
  43. }
  44.  
  45. bool update(int BITree[], int l, int r, int n, int val)
  46. {
  47.     return updateBIT(BITree, n, l, val);
  48.     // updateBIT(BITree, n, r+1, -val);
  49. }
  50.  
  51. void printtree(int BITree[], int n){
  52. 	for(int i=0;i<=n;i++)
  53. 		cout<<BITree[i]<<" ";
  54. 	cout<<"\n";
  55. }
  56.  
  57. int main()
  58. {
  59. 	int t = 1;
  60. 	while(t-->0){
  61. 		nemE.clear();
  62. 		map<int,int>::key_compare mycomp = nemE.key_comp();
  63.  
  64.  
  65. 		// memset(temp, -1, sizeof temp);
  66.  
  67. 		int n,u;
  68. 		cin>>n>>u;
  69. 		int arr[n], val[n];
  70. 		for(int i=0;i<n;i++){
  71. 			cin>>val[i];
  72. 			arr[i] =0;
  73. 		}
  74.     	// int *BITree = constructBITree(val, n);
  75.     	int BITree[n+1];
  76.     	memset(BITree, 0, sizeof BITree);
  77.  
  78.     	int strt = 0, end = n-1;
  79.  
  80.     	for(int i=0;i<u;i++){
  81.     		// printtree(BITree, n);
  82.     		int cs ;
  83.     		cin>>cs;
  84.     		if(cs==1){
  85.     			int k,x;
  86.     			cin>>k>>x;
  87.     			if(!(end<(k-1))){
  88.     				if(strt==k-1)
  89.     					strt++;
  90.     				update(BITree, k-1, n, n, 1);
  91.     				end++;
  92.     			}
  93.     			bool upd = true;
  94.     			for (map<int,int>::iterator it=nemE.upper_bound(k-1);
  95.     					it!=nemE.end(); ++it){
  96.     				upd = false;
  97.     				cout<<"updated"<<endl;
  98.     				int ta = it->first, tb = it->second;
  99.     				nemE.erase(it);
  100.    					nemE.insert(make_pair(ta+1, it->second));
  101.    				}
  102.    				if(upd)
  103.     				nemE.insert(make_pair(k-1, x));
  104.  
  105.     			// cout<<"map = ";
  106.     			// for(map<int,int>::iterator it=nemE.begin();it!=nemE.end(); ++it)
  107.     			// 	cout<<it->first<<"-->"<<it->second<<" ";
  108.     			// cout<<endl;
  109.  
  110.  
  111.     		}
  112.     		else
  113.     		if(cs==2){
  114.     			int k;
  115.     			cin>>k;
  116.     			if((k-1)<=end)
  117.     				end--;
  118.     			if(strt<=k-1){
  119.     				update(BITree, k-1, n, n, -1);
  120.     			}
  121.     			else{
  122.     				update(BITree, 0, n, n, -1);	
  123.     				strt--;
  124.     			}
  125.     			for (map<int,int>::iterator it=nemE.upper_bound(k-1);
  126.     						it!=nemE.end(); it++){
  127.     				// cout<<it->first<<" "<<it->second<<endl;
  128.     				int ta = it->first, tb = it->second;
  129.     				nemE.erase(it);
  130. 	    			nemE.insert(make_pair(ta-1, tb));
  131.     			}
  132.     			std::map<int,int>::iterator it;
  133.  
  134.   				it = nemE.find(k-1);
  135.   				if (it != nemE.end())
  136.     				nemE.erase (it);
  137.  
  138.  
  139.     		}
  140.     		else
  141.     		if(cs==3){
  142.     			int k;
  143.     			cin>>k;
  144.     			if(nemE.count(k-1)==1){
  145.     				cout<<nemE.at(k-1)<<"\n";
  146.     			}
  147.     			else{
  148.     				int po = getSum(BITree, k+1);
  149.     				// cout<<k<<" "<<po<<endl;
  150.     				cout<<val[k-po-1]<<"\n";
  151.     			}
  152.     		}
  153.     		// printtree(BITree, n);
  154.     	}
  155.  
  156. 	}
  157.  
  158.     return 0;
  159. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
6 10
1 2 4 8 16 32
3 4
1 1 7
3 2
2 2
2 2
3 2
1 6 666
3 6
2 1
3 1
3 50
stdout
copy 
8
1
4
666
4
https://ideone.com/60M2ok
ADALIST - Ada and List
language:
C++14 (gcc 8.3)
created:
9 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!