Guest User

Untitled

a guest
Dec 26th, 2022
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  6. #define F first
  7. #define S second
  8. #define sz(x) (int)(x.size())
  9. #define nl '\n'
  10.  
  11. typedef pair <int, int> pii;
  12.  
  13. const int N = 1e6+5;
  14. const int inf = INT_MAX;
  15.  
  16. int n, q, block, a[N];
  17. vector <pii> b;
  18.  
  19. void build(){
  20.     b.assign(block + 5, {inf, -inf});
  21.     for(int i = 0; i < n; i++){
  22.         b[i/block].F = min(b[i/block].F, a[i]);
  23.         b[i/block].S = max(b[i/block].S, a[i]);
  24.     }
  25. }
  26.  
  27. void upd(int pos, int val){
  28.     int blk = pos / block;
  29.     a[pos] = val;
  30.     for(int i = blk * block; i < min(n, block * (blk+1)); i++){
  31.         b[i/block].F = min(b[i/block].F, a[i]);
  32.         b[i/block].S = max(b[i/block].S, a[i]);
  33.     }
  34. }
  35.  
  36. bool get(int l, int r){
  37.     int mn = inf, mx = -inf;
  38.     while(l <= r){
  39.         if(l % block == 0 && l + block - 1 <= r){
  40.             mn = min(mn, b[l/block].F);
  41.             mx = max(mx, b[l/block].S);
  42.             l += block;
  43.         }
  44.         else{
  45.             mn = min(mn, a[l]);
  46.             mx = max(mx, a[l]);
  47.             l++;
  48.         }
  49.     }
  50.     return mx == mn;
  51. }
  52.  
  53. void solve(){
  54.     cin >> n;
  55.     block = sqrt(n);
  56.     for(int i = 0; i < n; i++)
  57.         cin >> a[i];
  58.     build();
  59.     cin >> q;
  60.     while(q--){
  61.         int t, x, y;
  62.         cin >> t >> x >> y;
  63.         if(t == 1){
  64.             if(get(--x, --y))
  65.                 cout << "draw\n";
  66.             else
  67.                 cout << "wins\n";
  68.         }
  69.         else
  70.             upd(--x, y);
  71.     }
  72. }
  73.  
  74. int main(){
  75.     speed;
  76.     //freopen("input.txt","r",stdin);
  77.     //freopen("output.txt","w",stdout);
  78.     int T = 1;
  79.     while(T--)
  80.         solve();
  81.     #ifndef ONLINE_JUDGE
  82.         cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  83.     #endif
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment