Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define F first
- #define S second
- #define sz(x) (int)(x.size())
- #define nl '\n'
- typedef pair <int, int> pii;
- const int N = 1e6+5;
- const int inf = INT_MAX;
- int n, q, block, a[N];
- vector <pii> b;
- void build(){
- b.assign(block + 5, {inf, -inf});
- for(int i = 0; i < n; i++){
- b[i/block].F = min(b[i/block].F, a[i]);
- b[i/block].S = max(b[i/block].S, a[i]);
- }
- }
- void upd(int pos, int val){
- int blk = pos / block;
- a[pos] = val;
- for(int i = blk * block; i < min(n, block * (blk+1)); i++){
- b[i/block].F = min(b[i/block].F, a[i]);
- b[i/block].S = max(b[i/block].S, a[i]);
- }
- }
- bool get(int l, int r){
- int mn = inf, mx = -inf;
- while(l <= r){
- if(l % block == 0 && l + block - 1 <= r){
- mn = min(mn, b[l/block].F);
- mx = max(mx, b[l/block].S);
- l += block;
- }
- else{
- mn = min(mn, a[l]);
- mx = max(mx, a[l]);
- l++;
- }
- }
- return mx == mn;
- }
- void solve(){
- cin >> n;
- block = sqrt(n);
- for(int i = 0; i < n; i++)
- cin >> a[i];
- build();
- cin >> q;
- while(q--){
- int t, x, y;
- cin >> t >> x >> y;
- if(t == 1){
- if(get(--x, --y))
- cout << "draw\n";
- else
- cout << "wins\n";
- }
- else
- upd(--x, y);
- }
- }
- int main(){
- speed;
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- int T = 1;
- while(T--)
- solve();
- #ifndef ONLINE_JUDGE
- cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment