Submission #1265664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265664		abramazani	ZIGZAG (INOI20_zigzag)	C++20	100 / 100	586 ms	133360 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef string str;
typedef pair<ll,ll> pll;
#define pb push_back
#define loop(i,s,n) for(ll i=s; i<n; i++)
#define loop_m(i,e,n) for(ll i=n; i>e; i--)
#define mkp make_pair
#define el "\n"

const ll maxn = 3e5 + 5;
ll aa[maxn];

struct Node{
  ll l, r, left, right, ptl1, ptl2, ptr1, ptr2, ans, lv, rv;
  ll add=0, mul=1;
};

Node seg[4*maxn];

void update_after_push(Node &a, Node &b, Node &c){
  // update ptl1:
  if (b.ptl1 < b.r-1)a.ptl1 = b.ptl1;
  else if ((b.r-b.l)%2) {
    if (b.rv>c.lv)a.ptl1 = c.ptl2;
    else a.ptl1 = b.ptl1;
  }else {
    if (b.rv<c.lv)a.ptl1 = c.ptl1;
    else a.ptl1 = b.ptl1;
  }

  // update ptl2:
  if (b.ptl2 < b.r-1)a.ptl2 = b.ptl2;
  else if ((b.r-b.l)%2) {
    if (b.rv<c.lv)a.ptl2 = c.ptl1;
    else a.ptl2 = b.ptl2;
  }else {
    if (b.rv>c.lv)a.ptl2 = c.ptl2;
    else a.ptl2 = b.ptl2;
  }

  // update ptr1:
  if (c.ptr1 > c.l)a.ptr1 = c.ptr1;
  else if ((c.r-c.l)%2) {
    if (c.lv>b.rv)a.ptr1 = b.ptr2;
    else a.ptr1 = c.ptr1;
  }else {
    if (c.lv<b.rv)a.ptr1 = b.ptr1;
    else a.ptr1 = c.ptr1;
  }

  // update ptr2:
  if (c.ptr2 > c.l)a.ptr2 = c.ptr2;
  else if ((c.r-c.l)%2) {
    if (c.lv<b.rv)a.ptr2 = b.ptr1;
    else a.ptr2 = c.ptr2;
  }else {
    if (c.lv>b.rv)a.ptr2 = b.ptr2;
    else a.ptr2 = c.ptr2;
  }

  a.ans = b.ans + c.ans + (b.rv>c.lv?(b.r-b.ptr1)*(c.ptl2-c.l+1):0) + (b.rv<c.lv?(b.r-b.ptr2)*(c.ptl1-c.l+1):0);
  a.lv = b.lv;
  a.rv = c.rv;
  //cout << "[" << a.l << "," << a.r << ") updated and ans is " << a.ans << " " << b.ans << " " << c.ans << el;
}

void init(ll node, ll l, ll r){
  seg[node].l = l, seg[node].r = r;

  if (seg[node].r-seg[node].l<=1){
    seg[node].ptl1 = seg[node].ptl2 = l;
    seg[node].ptr1 = seg[node].ptr2 = l;
    seg[node].lv = seg[node].rv = aa[l];
    seg[node].ans = 1;
    return;
  }

  seg[node].left = (node << 1), seg[node].right = (seg[node].left | 1);
  ll mid = (l+r) >> 1;
  init(seg[node].left, l, mid);
  init(seg[node].right, mid, r);
  update_after_push(seg[node], seg[seg[node].left], seg[seg[node].right]);
}

void update_lazy(ll node){
  seg[seg[node].left].lv *= seg[node].mul;
  seg[seg[node].left].lv += seg[node].add;
  seg[seg[node].left].rv *= seg[node].mul;
  seg[seg[node].left].rv += seg[node].add;

  seg[seg[node].right].lv *= seg[node].mul;
  seg[seg[node].right].lv += seg[node].add;
  seg[seg[node].right].rv *= seg[node].mul;
  seg[seg[node].right].rv += seg[node].add;
  
  if (seg[node].mul==-1){
    swap(seg[seg[node].left].ptl1, seg[seg[node].left].ptl2);
    swap(seg[seg[node].left].ptr1, seg[seg[node].left].ptr2);
    swap(seg[seg[node].right].ptl1, seg[seg[node].right].ptl2);
    swap(seg[seg[node].right].ptr1, seg[seg[node].right].ptr2);
    
    seg[seg[node].left].mul *= -1;
    seg[seg[node].right].mul *= -1;
    seg[seg[node].left].add *= -1;
    seg[seg[node].right].add *= -1;
  }
  seg[seg[node].left].add += seg[node].add;
  seg[seg[node].right].add += seg[node].add;
  
  seg[node].mul = 1;
  seg[node].add = 0;
}

void update(ll node, ll l, ll r, bool mnz, ll x=0){
  if (seg[node].l>=r or seg[node].r<=l)return;
  if (seg[node].l>=l and seg[node].r<=r){
    if (mnz){
      swap(seg[node].ptl1, seg[node].ptl2);
      swap(seg[node].ptr1, seg[node].ptr2);
      seg[node].rv *= -1;
      seg[node].lv *= -1;
      seg[node].mul *= -1;
      seg[node].add *= -1;
    }else {
      seg[node].rv += x;
      seg[node].lv += x;
      seg[node].add += x;
    }
    return;
  }
  update_lazy(node);
  update(seg[node].left, l, r, mnz, x);
  update(seg[node].right, l, r, mnz, x);
  update_after_push(seg[node], seg[seg[node].left], seg[seg[node].right]);
}

Node get(ll node, ll l, ll r){
  if (seg[node].l>=r or seg[node].r<=l){
    Node res;res.ans=0;
    return res;
  }
  if (seg[node].l>=l and seg[node].r<=r)return seg[node];

  update_lazy(node);
  
  Node a = get(seg[node].left, l, r), b = get(seg[node].right, l, r), res;
  if (a.ans==0)return b;
  else if (b.ans==0)return a;

  res.l = a.l, res.r = b.r;

  update_after_push(res, a, b);
  return res;
}

void solve() {
  ll n,q;cin >> n >> q;
  loop(i, 0, n)cin >> aa[i];
  init(1, 0, n);
  while(q--){
    char tp;ll li, ri;cin >> tp >> li >> ri;li--;
    if (tp=='+'){
      ll xi;cin >> xi;
      update(1, li, ri, 0, xi);
    }else if (tp=='*'){
      update(1, li, ri, 1);
    }else cout << get(1, li, ri).ans << el;
  }
  cout << el;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  ll t=1;//cin >> t;
  while(t--)solve();
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15