oj.uz

Submission #1003578

# Submission time Handle Problem Language Result Execution time Memory
1003578 2024-06-20T13:14:05 Z vjudge1 ZIGZAG (INOI20_zigzag) C++17
100 / 100
 1065 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;
      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 11 ms 2652 KB Output is correct
2 Correct 10 ms 2652 KB Output is correct
3 Correct 10 ms 2652 KB Output is correct
4 Correct 12 ms 2780 KB Output is correct
5 Correct 13 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2764 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 137820 KB Output is correct
2 Correct 189 ms 2620 KB Output is correct
3 Correct 635 ms 140624 KB Output is correct
4 Correct 842 ms 140672 KB Output is correct
5 Correct 698 ms 140776 KB Output is correct
6 Correct 804 ms 140612 KB Output is correct
7 Correct 683 ms 137552 KB Output is correct
8 Correct 783 ms 140628 KB Output is correct
9 Correct 724 ms 140628 KB Output is correct
10 Correct 635 ms 140740 KB Output is correct
11 Correct 712 ms 140636 KB Output is correct
12 Correct 744 ms 140796 KB Output is correct
13 Correct 509 ms 140884 KB Output is correct
14 Correct 585 ms 140764 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 10 ms 2652 KB Output is correct
3 Correct 10 ms 2652 KB Output is correct
4 Correct 12 ms 2780 KB Output is correct
5 Correct 13 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2764 KB Output is correct
8 Correct 252 ms 45908 KB Output is correct
9 Correct 238 ms 45904 KB Output is correct
10 Correct 253 ms 47176 KB Output is correct
11 Correct 208 ms 46672 KB Output is correct
12 Correct 344 ms 47044 KB Output is correct
13 Correct 290 ms 47180 KB Output is correct
14 Correct 248 ms 46992 KB Output is correct
15 Correct 261 ms 46048 KB Output is correct
16 Correct 271 ms 47136 KB Output is correct
17 Correct 259 ms 46944 KB Output is correct
18 Correct 172 ms 46928 KB Output is correct
19 Correct 170 ms 47184 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2652 KB Output is correct
2 Correct 10 ms 2652 KB Output is correct
3 Correct 10 ms 2652 KB Output is correct
4 Correct 12 ms 2780 KB Output is correct
5 Correct 13 ms 2648 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 10 ms 2764 KB Output is correct
8 Correct 761 ms 137820 KB Output is correct
9 Correct 189 ms 2620 KB Output is correct
10 Correct 635 ms 140624 KB Output is correct
11 Correct 842 ms 140672 KB Output is correct
12 Correct 698 ms 140776 KB Output is correct
13 Correct 804 ms 140612 KB Output is correct
14 Correct 683 ms 137552 KB Output is correct
15 Correct 783 ms 140628 KB Output is correct
16 Correct 724 ms 140628 KB Output is correct
17 Correct 635 ms 140740 KB Output is correct
18 Correct 712 ms 140636 KB Output is correct
19 Correct 744 ms 140796 KB Output is correct
20 Correct 509 ms 140884 KB Output is correct
21 Correct 585 ms 140764 KB Output is correct
22 Correct 252 ms 45908 KB Output is correct
23 Correct 238 ms 45904 KB Output is correct
24 Correct 253 ms 47176 KB Output is correct
25 Correct 208 ms 46672 KB Output is correct
26 Correct 344 ms 47044 KB Output is correct
27 Correct 290 ms 47180 KB Output is correct
28 Correct 248 ms 46992 KB Output is correct
29 Correct 261 ms 46048 KB Output is correct
30 Correct 271 ms 47136 KB Output is correct
31 Correct 259 ms 46944 KB Output is correct
32 Correct 172 ms 46928 KB Output is correct
33 Correct 170 ms 47184 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 973 ms 137812 KB Output is correct
37 Correct 915 ms 140884 KB Output is correct
38 Correct 687 ms 140032 KB Output is correct
39 Correct 991 ms 140940 KB Output is correct
40 Correct 921 ms 137812 KB Output is correct
41 Correct 868 ms 140972 KB Output is correct
42 Correct 844 ms 138124 KB Output is correct
43 Correct 976 ms 140860 KB Output is correct
44 Correct 1033 ms 140840 KB Output is correct
45 Correct 1065 ms 141092 KB Output is correct
46 Correct 918 ms 140880 KB Output is correct
47 Correct 841 ms 141240 KB Output is correct