Advertisement
mickypinata

TOI11: Cannons At The Fort

Apr 22nd, 2020
620
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int cannons[10000010];
  6. int nc, nload, T, range;
  7.  
  8. int main(){
  9.  
  10.     int x, mxpos;
  11.  
  12.     scanf("%d %d %d %d", &nc, &nload, &T, &range);
  13.     mxpos = 0;
  14.     for(int i = 1; i <= nc; ++i){
  15.         scanf("%d", &x);
  16.         ++x;
  17.         ++cannons[x];
  18.         mxpos = max(mxpos, x);
  19.     }
  20.  
  21.     for(int i = 1; i <= mxpos; ++i){
  22.         cannons[i] += cannons[i - 1];
  23.     }
  24.  
  25.     for(int k = 0; k < T; ++k){
  26.         int cnt = 0;
  27.         int last = 0;
  28.         for(int i = 0; i < nload; ++i){
  29.             scanf("%d", &x);
  30.             ++x;
  31.             int s = max(last + 1, x - range);
  32.             int e = min(mxpos, x + range);
  33.             if(s > e){
  34.                 continue;
  35.             }
  36.             cnt += cannons[e] - cannons[s - 1];
  37.             last = e;
  38.         }
  39.         cout << cnt << "\n";
  40.     }
  41.  
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement