oj.uz

Submission #1003577

# Submission time Handle Problem Language Result Execution time Memory
1003577 2024-06-20T13:12:44 Z fuad27 ZIGZAG (INOI20_zigzag) C++17
100 / 100
 1064 ms 141240 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T, typename F>
struct ST {
  vector<T> t;
  vector<F> lz;
  T def;
  int n;
  ST(){}
  ST(int N) {
    n=N;
    t=vector<T>(4*n);
    lz=vector<F>(4*n);
  }
  void build(T a[], int tl, int tr, int v) {
    lz[v]=F(tl,tr);
    if(tl==tr) {
      t[v]=a[tl];
      return;
    }
    int tm=(tl+tr)/2;
    build(a,tl,tm,2*v);
    build(a,tm+1,tr,2*v+1);
    t[v]=merge(t[2*v],t[2*v+1]);
  }
  void push(int v) {
    lz[2*v].compose(lz[v]);
    lz[2*v+1].compose(lz[v]);
    t[v]=lz[v].applyAggregate(t[v]);
    int l=lz[v].l,r=lz[v].r;
    lz[v]=F(l,r);
  }
  T query(int l, int r, int tl, int tr, int v) {
    if(l>tr or r<tl)return def;
    if(l<=tl and tr<=r)return lz[v].applyAggregate(t[v]);
    push(v);
    int tm=(tl+tr)/2;
    return merge(query(l,r,tl,tm,2*v),query(l,r,tm+1,tr,2*v+1));
  }
  void update(int l, int r, F upd, int tl, int tr, int v) {
    if(r<tl or tr<l)return;
    if(l<=tl and tr<=r) {
      lz[v].compose(upd);
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    update(l,r,upd,tl,tm,2*v);
    update(l,r,upd,tm+1,tr,2*v+1);
    t[v]=merge(lz[2*v].applyAggregate(t[2*v]),lz[2*v+1].applyAggregate(t[2*v+1]));
  }
  void update(int at, T val, int tl, int tr, int v) {
    if(tl==tr) {
      t[v]=val;
      lz[v]=F(tl,tr);
      return;
    }
    int tm=(tl+tr)/2; 
    push(v);
    if(at<=tm)update(at,val,tl,tm,2*v);
    else update(at,val,tm+1,tr,2*v+1);
    t[v]=merge(lz[2*v].applyAggregate(t[2*v]),lz[2*v+1].applyAggregate(t[2*v+1]));
  }
  T query(int l, int r){return query(l,r,0,n-1,1);}
  void update(int l, int r, F upd){update(l,r,upd,0,n-1,1);}
  void update(int at, T val){update(at,val,0,n-1,1);}
  void build(T a[]){build(a,0,n-1,1);}
};
#define int long long

struct node {
  int Lval, Rval;
  int Ld=0, Li=0, Rd=0,Ri=0;
  long long ans=0;
  int sz=0;
  node(){}
  node(int val) {
    sz=Ld=Li=Rd=Ri=1;
    ans=1;
    Lval=Rval=val;
  }
};
node merge(node L, node R) {
  if(L.sz == 0)return R;
  else if(R.sz == 0)return L;
  node res;
  res.Lval = L.Lval;
  res.Rval = R.Rval;
  res.sz = L.sz+R.sz;
  res.Ld = L.Ld;
  res.Li = L.Li;
  res.Rd = R.Rd;
  res.Ri = R.Ri;
  res.ans = L.ans+R.ans;
  if(L.Rval > R.Lval) {
    res.ans -= L.Rd*(L.Rd+1)/2;
    res.ans -= R.Li*(R.Li+1)/2;
    long long sz = L.Rd + R.Li;
    res.ans += sz*(sz+1)/2;
    if(R.sz == R.Li) {
      if(R.sz%2 == 1) {
        res.Ri = sz;
      }
      else {
        res.Rd = sz;
      }
    }
    if(L.sz == L.Rd) {
      if(L.sz%2 == 1) {
        res.Ld = sz;
      }
      else {
        res.Li = sz;
      }
    }
  }
  else if(L.Rval < R.Lval) {
    res.ans -= L.Ri*(L.Ri+1)/2;
    res.ans -= R.Ld*(R.Ld+1)/2;
    long long sz = L.Ri + R.Ld;
    res.ans += sz*(sz+1)/2;
    if(R.sz == R.Ld) {
      if(R.sz%2 == 1) {
        res.Rd = sz;
      }
      else {
        res.Ri = sz;
      }
    }
    if(L.sz == L.Ri) {
      if(L.sz%2 == 1) {
        res.Li = sz;
      }
      else {
        res.Ld = sz;
      }
    }
  }
  return res;
}
struct F {
  int add=0, mult=0;
  int l, r;
  F(){}
  F(int tl, int tr){}
  node applyAggregate(node T) {
    if(mult%2 == 1) {
      T.Rval*=-1;
      T.Lval*=-1;
      swap(T.Rd, T.Ri);
      swap(T.Ld, T.Li);
    }
    T.Rval += add;
    T.Lval += add;
    return T;
  }
  void compose(F parent) {
    if(parent.mult%2 == 1) {
      add*=-1;
      mult+=parent.mult;
    }
    add+=parent.add;
  }
};
signed main () {
  int n,q;
  cin >> n >> q;
  node A[n];
  ST<node, F> st(n);
  for(int i =0 ;i<n;i++) {
    int val;
    cin >> val;
    A[i] = node(val);
  }
  st.build(A);
  while(q--) {
    char c;
    cin >> c;
    if(c=='?'){ 
      int l, r;
      cin >> l >> r;
      l--,r--;
      cout << st.query(l, r).ans << "\n";
    }
    else if(c == '*') {
      int l, r;
      cin >> l >> r;
      l--,r--;
      F upd;
      upd.mult = 1;
//      for(int i = l;i<=r;i++) {
//        A[i]*=-1;
//        update(i, upd);
//      }
      st.update(l, r, upd);
    }
    else if(c == '+') {
      int l, r, val;
      cin >> l >> r >> val;
      l--,r--;
      F upd;
      upd.add = val;
      st.update(l, r, upd);
      //for(int i = l;i<=r;i++) {
      //  A[i]+=val;
      //  update(i, upd);
      //}
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2652 KB Output is correct
2 Correct 11 ms 2776 KB Output is correct
3 Correct 11 ms 2652 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 137596 KB Output is correct
2 Correct 194 ms 2608 KB Output is correct
3 Correct 742 ms 141028 KB Output is correct
4 Correct 939 ms 140880 KB Output is correct
5 Correct 822 ms 140724 KB Output is correct
6 Correct 911 ms 140736 KB Output is correct
7 Correct 800 ms 137716 KB Output is correct
8 Correct 836 ms 140788 KB Output is correct
9 Correct 752 ms 140628 KB Output is correct
10 Correct 660 ms 140872 KB Output is correct
11 Correct 761 ms 140704 KB Output is correct
12 Correct 772 ms 140628 KB Output is correct
13 Correct 562 ms 140884 KB Output is correct
14 Correct 574 ms 140808 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2652 KB Output is correct
2 Correct 11 ms 2776 KB Output is correct
3 Correct 11 ms 2652 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct
8 Correct 268 ms 45956 KB Output is correct
9 Correct 254 ms 45904 KB Output is correct
10 Correct 290 ms 47196 KB Output is correct
11 Correct 210 ms 46748 KB Output is correct
12 Correct 325 ms 47032 KB Output is correct
13 Correct 261 ms 47188 KB Output is correct
14 Correct 248 ms 47200 KB Output is correct
15 Correct 282 ms 45924 KB Output is correct
16 Correct 269 ms 47084 KB Output is correct
17 Correct 284 ms 47184 KB Output is correct
18 Correct 190 ms 46944 KB Output is correct
19 Correct 169 ms 46932 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2652 KB Output is correct
2 Correct 11 ms 2776 KB Output is correct
3 Correct 11 ms 2652 KB Output is correct
4 Correct 11 ms 2752 KB Output is correct
5 Correct 9 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct
8 Correct 830 ms 137596 KB Output is correct
9 Correct 194 ms 2608 KB Output is correct
10 Correct 742 ms 141028 KB Output is correct
11 Correct 939 ms 140880 KB Output is correct
12 Correct 822 ms 140724 KB Output is correct
13 Correct 911 ms 140736 KB Output is correct
14 Correct 800 ms 137716 KB Output is correct
15 Correct 836 ms 140788 KB Output is correct
16 Correct 752 ms 140628 KB Output is correct
17 Correct 660 ms 140872 KB Output is correct
18 Correct 761 ms 140704 KB Output is correct
19 Correct 772 ms 140628 KB Output is correct
20 Correct 562 ms 140884 KB Output is correct
21 Correct 574 ms 140808 KB Output is correct
22 Correct 268 ms 45956 KB Output is correct
23 Correct 254 ms 45904 KB Output is correct
24 Correct 290 ms 47196 KB Output is correct
25 Correct 210 ms 46748 KB Output is correct
26 Correct 325 ms 47032 KB Output is correct
27 Correct 261 ms 47188 KB Output is correct
28 Correct 248 ms 47200 KB Output is correct
29 Correct 282 ms 45924 KB Output is correct
30 Correct 269 ms 47084 KB Output is correct
31 Correct 284 ms 47184 KB Output is correct
32 Correct 190 ms 46944 KB Output is correct
33 Correct 169 ms 46932 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1061 ms 137840 KB Output is correct
37 Correct 1034 ms 140880 KB Output is correct
38 Correct 682 ms 139980 KB Output is correct
39 Correct 995 ms 141008 KB Output is correct
40 Correct 952 ms 137888 KB Output is correct
41 Correct 901 ms 141012 KB Output is correct
42 Correct 857 ms 138060 KB Output is correct
43 Correct 971 ms 140864 KB Output is correct
44 Correct 1064 ms 140880 KB Output is correct
45 Correct 1020 ms 141140 KB Output is correct
46 Correct 935 ms 140876 KB Output is correct
47 Correct 848 ms 141240 KB Output is correct