fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1<<20;
  7. const int TREE_SIZE = N<<2;
  8.  
  9. int tests,current_case;
  10. int n,a[N],q;
  11. vector < pair < int, int > > v[N];
  12. int tree[TREE_SIZE];
  13. int ans[N];
  14.  
  15. void message(int current_case) {
  16.     //cerr<<"Case "<<current_case<<" solved!"<<endl;
  17.     fprintf(stderr, "Case %d solved!\n", current_case);
  18. }
  19.  
  20. void update_tree(int a, int b, int pos, int node, int value) {
  21.     if(a>b || a>pos || b<pos) return;
  22.     if(a==b) {
  23.         tree[node]=value;
  24.         return;
  25.     }
  26.     update_tree(a,(a+b)>>1,pos,node<<1,value);
  27.     update_tree(((a+b)>>1)+1,b,pos,(node<<1)|1,value);
  28.     tree[node]=min(tree[node<<1],tree[(node<<1)|1]);
  29. }
  30.  
  31. int query_tree(int a, int b, int node, int value) {
  32.     if(a==b) return a;
  33.     if(tree[node<<1]<value) return query_tree(a,(a+b)>>1,node<<1,value);
  34.     else return query_tree(((a+b)>>1)+1,b,(node<<1)|1,value);
  35. }
  36.  
  37. int main() {
  38.     //ios_base::sync_with_stdio(false);
  39.     //cin.tie(NULL);
  40.     int i,j,x,y;
  41.  
  42.     tests=1;
  43.     //scanf("%d", &tests);
  44.     //cin>>tests;
  45.     for(current_case=1;current_case<=tests;current_case++) {
  46.         scanf("%d", &n);
  47.         for(i=1;i<=n;i++) {
  48.             scanf("%d", &a[i]);
  49.             ++a[i];
  50.         }
  51.         scanf("%d", &q);
  52.         for(i=1;i<=q;i++) {
  53.             scanf("%d %d", &x, &y);
  54.             v[y].push_back(make_pair(x,i));
  55.         }
  56.         for(i=1;i<=n;i++) {
  57.             update_tree(1,1000001,a[i],1,i);
  58.             for(j=0;j<(int)(v[i].size());j++) ans[v[i][j].second]=query_tree(1,1000001,1,v[i][j].first); 
  59.         }
  60.         for(i=1;i<=q;i++) {
  61.             printf("%d\n", ans[i]-1);
  62.         }
  63.  
  64.         MESSAGE:
  65.         message(current_case);
  66.     }
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout #stderr 0s 64392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Case 1 solved!
https://ideone.com/P2tBs5
language:
C++14 (gcc 8.3)
created:
7 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!