Submission #1003588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003588		aykhn	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	967 ms	104532 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 3e5 + 5;
const int LOG = 20;
const int mod = 1e9 + 7;

struct SegTree
{
  int n;
  vector<int> st;
  vector<array<int, 2>> lz;
  void init(int N)
  {
    n = N;
    st.assign((n + 5) << 2, 0);
    lz.assign((n + 5) << 2, {0, 0});
  }
  void relax(int l, int r, int x)
  {
    if (!lz[x][0] && !lz[x][1]) return;
    if (lz[x][0])
    {
      st[x] *= -1;
    }
    st[x] += lz[x][1];
    if (l == r)
    {
      lz[x] = {0, 0};
      return;
    }
    if (lz[x][0]) lz[2*x][1] *= -1, lz[2*x + 1][1] *= -1, lz[2*x][0] ^= 1, lz[2*x + 1][0] ^= 1;
    lz[2*x][1] += lz[x][1], lz[2*x + 1][1] += lz[x][1];
    lz[x] = {0, 0};
  }
  void add(int l, int r, int x, int lx, int rx, int val)
  {
    relax(l, r, x);
    if (l > rx || r < lx) return;
    if (l >= lx && r <= rx)
    {
      if (val == inf)
      {
        lz[x][1] *= -1;
        lz[x][0] ^= 1;
      }
      else
      {
        lz[x][1] += val;
      }
      relax(l, r, x);
      // cout << l << ' ' << r << ' ' << st[x] << '\n';
      return;
    }
    int mid = (l + r) >> 1;
    add(l, mid, 2*x, lx, rx, val);
    add(mid + 1, r, 2*x + 1, lx, rx, val);
  }
  int get(int l, int r, int x, int lx, int rx)
  {
    relax(l, r, x);
    if (l > rx || r < lx) return 0;
    if (l >= lx && r <= rx) return st[x];
    int mid = (l + r) >> 1;
    return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
    // cout << l << ' ' << r << ' ' << st[x].ans << ' ' << brute(l, r) << ' ' << st[x].p0 << ' ' << st[x].p1 << ' ' << st[x].s0 << ' ' << st[x].s1 << ' ' << st[x].t << ' ' << st[x].L << ' ' << st[x].R << '\n';
  }
};

struct DATA
{
  int p0 = 0, p1 = 0, s0 = 0, s1 = 0, ans = 0, l = 0, r = 0;
};

int n;
DATA st[MXN << 2];
int lz[MXN << 2];
int a[MXN], val[MXN];

DATA combine(DATA a, DATA b)
{
  if (a.p0 == -1) return b;
  if (b.p0 == -1) return a;
  int sza = a.r - a.l + 1, szb = b.r - b.l + 1;
  DATA res;
  res.ans = a.ans + b.ans;
  res.ans += a.s1 * b.p0;
  res.ans += a.s0 * b.p1;
  res.p0 = a.p0, res.p1 = a.p1;
  res.s0 = b.s0, res.s1 = b.s1;
  if (a.p0 == sza)
  {
    if ((sza & 1)) res.p0 += b.p1;
    else res.p0 += b.p0;
  }
  if (a.p1 == sza)
  {
    if ((sza & 1)) res.p1 += b.p0;
    else res.p1 += b.p1;
  }
  if (b.s0 == szb)
  {
    if ((szb & 1)) res.s0 += a.s1;
    else res.s0 += a.s0;
  }
  if (b.s1 == szb)
  {
    if ((szb & 1)) res.s1 += a.s0;
    else res.s1 += a.s1;
  }
  res.l = a.l, res.r = b.r;
  return res;
}

void build(int l, int r, int x)
{
  if (l == r)
  {
    st[x] = {(val[l] == 0), (val[l] == 1), (val[l] == 0), (val[l] == 1), (val[l] != 2), l, l};
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, 2*x), build(mid + 1, r, 2*x + 1);
  st[x] = combine(st[2*x], st[2*x + 1]);
}
void relax(int l, int r, int x)
{
  if (!lz[x]) return;
  swap(st[x].p0, st[x].p1);
  swap(st[x].s0, st[x].s1);
  lz[x] = 0;
  if (l == r) return;
  lz[2*x] ^= 1, lz[2*x + 1] ^= 1;
}
void upd(int l, int r, int x, int lx, int rx)
{
  relax(l, r, x);
  if (l > rx || r < lx) return;
  if (l >= lx && r <= rx)
  {
    lz[x] ^= 1;
    relax(l, r, x);
    return;
  }
  int mid = (l + r) >> 1;
  upd(l, mid, 2*x, lx, rx);
  upd(mid + 1, r, 2*x + 1, lx, rx);
  st[x] = combine(st[2*x], st[2*x + 1]);
}
void make(int l, int r, int x, int lx, int rx)
{
  relax(l, r, x);
  if (l > rx || r < lx) return;
  if (l >= lx && r <= rx)
  {
    if (l == n) st[x] = {-1, 0, 0, 0, 0, 0, 0};
    else st[x] = {(val[l] == 0), (val[l] == 1), (val[l] == 0), (val[l] == 1), (val[l] != 2), l, l};
    return;
  }
  int mid = (l + r) >> 1;
  make(l, mid, 2*x, lx, rx);
  make(mid + 1, r, 2*x + 1, lx, rx);
  st[x] = combine(st[2*x], st[2*x + 1]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
  if (lx > rx) return {0, 0, 0, 0, 0, 0, 0};
  if (l > rx || r < lx) return {-1, 0, 0, 0, 0, 0, 0};
  relax(l, r, x);
  if (l >= lx && r <= rx) return st[x];
  int mid = (l + r) >> 1;
  return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> n >> q;
  SegTree st1;
  st1.init(n);
  for (int i = 1; i <= n; i++) 
  {
    cin >> a[i];
    st1.add(1, n, 1, i, i, a[i]);
  }
  for (int i = 1; i < n; i++)
  {
    if (a[i] < a[i + 1]) val[i] = 0;
    else if (a[i] > a[i + 1]) val[i] = 1;
    else val[i] = 2;
  }
  build(1, n, 1);
  int f = 1;
  while (q--)
  {
    char ch;
    cin >> ch;
    if (ch == '?')
    {
      int l, r;
      cin >> l >> r;
      cout << get(1, n, 1, l, r - 1).ans + (r - l + 1) << '\n';
    }
    else if (ch == '+')
    {
      int l, r, v;
      cin >> l >> r >> v;
      st1.add(1, n, 1, l, r, v);
      if (n > 1 && l > 1)
      {
        int x = st1.get(1, n, 1, l - 1, l - 1);
        int y = st1.get(1, n, 1, l, l);
        if (x < y) val[l - 1] = 0;
        else if (x > y) val[l - 1] = 1;
        else val[l - 1] = 2;
        make(1, n, 1, l - 1, l - 1);
      }
      if (n > 1 && r < n)
      {
        int x = st1.get(1, n, 1, r, r);
        int y = st1.get(1, n, 1, r + 1, r + 1);
        if (x < y) val[r] = 0;
        else if (x > y) val[r] = 1;
        else val[r] = 2;
        make(1, n, 1, r, r);
      }
    }
    else if (ch == '*')
    {
      int l, r;
      cin >> l >> r;
      st1.add(1, n, 1, l, r, inf);
      upd(1, n, 1, l, r - 1);
      if (l > 1)
      {
        int x = st1.get(1, n, 1, l - 1, l - 1);
        int y = st1.get(1, n, 1, l, l);
        if (x < y) val[l - 1] = 0;
        else if (x > y) val[l - 1] = 1;
        else val[l - 1] = 2;
        make(1, n, 1, l - 1, l - 1);
      }
      if (r < n)
      {
        int x = st1.get(1, n, 1, r, r);
        int y = st1.get(1, n, 1, r + 1, r + 1);
        if (x < y) val[r] = 0;
        else if (x > y) val[r] = 1;
        else val[r] = 2;
        make(1, n, 1, r, r);
      }
    }
  }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:199:7: warning: unused variable 'f' [-Wunused-variable]
  199 |   int f = 1;
      |       ^

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