제출 #1003326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003326		vjudge1	ZIGZAG (INOI20_zigzag)	C++17	0 / 100	2020 ms	111312 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 DATA
{
  int p0 = 0, p1 = 0, s0 = 0, s1 = 0, L = 0, R = 0, ans = 0, t = 0, l = 0, r = 0;
};
struct LDATA
{
  int sw = 0, L = 0, R = 0; 
};

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



int brute(int s, int e)
{
  int res = e - s + 1;
  for (int i = s; i + 1 <= e; i++)
  {
    int f = 1;
    if (a[i] < a[i + 1])
    {
      for (int j = i + 1; j <= e; j++)
      {
        if ((j - i) & 1)
        {
          f &= (a[j - 1] < a[j]);
        }
        else 
        {
          f &= (a[j - 1] > a[j]);
        }
        res += f;
      }
    }
    else
    {
      for (int j = i + 1; j <= e; j++)
      {
        if ((j - i) & 1)
        {
          f &= (a[j - 1] > a[j]);
        }
        else 
        {
          f &= (a[j - 1] < a[j]);
        }
        res += f;
      }
    }
  }
  return res;
}

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;
  if (a.R < b.L) res.ans += a.s0 * b.p0;
  if (a.R > b.L) res.ans += a.s1 * b.p1;
  res.p0 = a.p0, res.p1 = a.p1;
  res.s0 = b.s0, res.s1 = b.s1;
  res.t = 3;
  if (a.t == 0 || a.t == 2)
  {
    if ((sza & 1) && a.R > b.L) res.p0 += b.p1;
    else if (!(sza & 1) && a.R < b.L) res.p0 += b.p0;
  }
  if (a.t == 1 || a.t == 2)
  {
    if ((sza & 1) && a.R < b.L) res.p1 += b.p0;
    else if (!(sza & 1) && a.R > b.L) res.p1 += b.p1;
  }
  if (b.t == 0 || b.t == 2)
  {
    if ((szb & 1) && a.R < b.L) res.s1 += a.s0;
    else if (!(szb & 1) && a.R < b.L) res.s0 += a.s0;
  }
  if (b.t == 1 || b.t == 2)
  {
    if ((szb & 1) && a.R > b.L) res.s0 += a.s1;
    else if (!(szb & 1) && a.R > b.L) res.s1 += a.s1;
  }
  if (a.t == 3 || b.t == 3) res.t = 3;
  else
  {
    if (a.t == 2 && b.t == 2) 
    {
      if (a.R < b.L) res.t = 1;
      else if (a.R > b.L) res.t = 0;
    }
    if (a.t == 2 && b.t <= 1) 
    {
      if (a.R < b.L) res.t = 1;
      else if (a.R > b.L) res.t = 0;
      if (1 - b.t != res.t) res.t = 3;
    }
    if (a.t == 1 && b.t == 1 && !(sza & 1)) res.t = 1;
    if (a.t == 1 && b.t == 0 && (sza & 1)) res.t = 1;
    if (a.t == 0 && b.t == 1 && (sza & 1)) res.t = 0;
    if (a.t == 0 && b.t == 0 && !(sza & 1)) res.t = 0;
  }
  res.L = a.L, res.R = b.R;
  res.l = a.l, res.r = b.r;
  return res;
}

void build(int l, int r, int x)
{
  if (l == r)
  {
    st[x] = {1, 1, 1, 1, a[l], a[l], 1, 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].sw && !lz[x].L && !lz[x].R) return;
  if (lz[x].sw)
  {
    st[x].L *= -1, st[x].R *= -1;
    swap(st[x].p0, st[x].p1);
    swap(st[x].s0, st[x].s1);
    if (st[x].t <= 1) st[x].t ^= 1;
  }
  st[x].L += lz[x].L, st[x].R += lz[x].R;
  if (l == r)
  {
    lz[x] = {0, 0, 0};
    return;
  }
  lz[2*x].sw ^= lz[x].sw, lz[2*x + 1].sw ^= lz[x].sw;
  lz[2*x].L += lz[x].L, lz[2*x + 1].L += lz[x].L;
  lz[2*x].R += lz[x].R, lz[2*x + 1].R += lz[x].R;
  lz[x] = {0, 0, 0};
}
void upd(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].sw ^= 1;
      lz[x].L *= -1;
      lz[x].R *= -1;
    }
    else
    {
      lz[x].L += val, lz[x].R += val;
    }
    relax(l, r, x);
    // 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';
    return;
  }
  int mid = (l + r) >> 1;
  upd(l, mid, 2*x, lx, rx, val);
  upd(mid + 1, r, 2*x + 1, lx, rx, val);
  st[x] = combine(st[2*x], st[2*x + 1]);
  // 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';
}
DATA get(int l, int r, int x, int lx, int rx)
{
  if (l > rx || r < lx) return {-1, 0, 0, 0, 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;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);
  while (q--)
  {
    char ch;
    cin >> ch;
    if (ch == '?')
    {
      int l, r;
      cin >> l >> r;
      cout << get(1, n, 1, l, r).ans << '\n';
      // cout << brute(l, r) << '\n';
    }
    else if (ch == '+')
    {
      int l, r, v;
      cin >> l >> r >> v;
      for (int i = l; i <= r; i++) a[i] += v;
      upd(1, n, 1, l, r, v);
      // cout << '\n';
    }
    else if (ch == '*')
    {
      int l, r;
      cin >> l >> r;
      for (int i = l; i <= r; i++) a[i] *= -1;
      upd(1, n, 1, l, r, inf);
      // cout << '\n';
    }
  }
}

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