Submission #1003578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003578		vjudge1	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	1065 ms	141240 KiB

Main

#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;
      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 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15