fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace{
  6.     // Types
  7.     #define ll long long
  8.     #define ull unsigned long long
  9.  
  10.     // Shortcuts
  11.     #define sp " "
  12.     #define endl "\n"
  13.     #define ft first
  14.     #define se second
  15.     #define pb push_back
  16.     #define pob pop_back
  17.     #define __Orion__ signed main()
  18.     #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  19.     #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  20.  
  21.     // Functions
  22.     #define sz(s) (s).size()
  23.     #define all(s) (s).begin(), (s).end()
  24.     #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  25.     #define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  26.     #define file(a) freopen(a".INP", "r", stdin); freopen(a".OUT", "w", stdout)
  27.  
  28.     // Const
  29.     const ll inf = 1e18;
  30.     const ll mod = 1e9 + 7;
  31.     const double pi = 3.1415926535897932384626433832795;
  32. }
  33. const int mx = 1e5 + 5;
  34. int n, t;
  35. ll ma, s[mx];
  36. bool k[10000005];
  37.  
  38. //sub1
  39. void solve1(){
  40.     vector<int> res; res.pb(0);
  41.     FOR(i, 1, n)
  42.         k[s[i]] = 1;
  43.     FOR(i, 1, 1e7) if(!k[i]) res.pb(i);
  44.     //for(auto x : res) cout << x << sp;
  45.     while(t--){
  46.         int tc; cin >> tc;
  47.         cout << res[tc] << endl;
  48.     }
  49. }
  50.  
  51. //sub2
  52. void solve2(){
  53.     while(t--){
  54.         ll tc; cin >> tc;
  55.         int i = 0;
  56.         while(1){
  57.             auto it = upper_bound(s + 1, s + n + 1, tc);
  58.             int pos = it - s - 1;
  59.             if(i == pos) break;
  60.             tc+=pos - i;
  61.             i = pos;
  62.         }
  63.         cout << tc << endl;
  64.     }
  65. }
  66.  
  67. __Orion__{
  68.     fast;
  69.     //file("test1");
  70.  
  71.     cin >> n >> t;
  72.     FOR(i, 1, n) cin >> s[i], ma = max(ma, s[i]);
  73.     sort(s + 1, s + n + 1);
  74.     if(ma <= 1e6) solve1();
  75.     else solve2();
  76.     cerr << "Time elapsed: " << TIME  << sp << "s." << endl;
  77.  
  78.     return (0 ^ 0);
  79. }
  80.  
Success #stdin #stdout #stderr 0.05s 69244KB
comments (?)
stdin
copy 
4 1
1 2 5 10
1
stdout
copy 
3
stderr
copy 
Time elapsed: 0.045213 s.
https://ideone.com/y8FCQ7
language:
C++14 (gcc 8.3)
created:
2 days 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!