oj.uz

답안 #1003580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003580 2024-06-20T13:19:00 Z vjudge1 ZIGZAG (INOI20_zigzag) C++17
42 / 100
 971 ms 1048576 KB 
#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)
  {
    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 (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, 1);
  int f = 1;
  while (q--)
  {
    char ch;
    cin >> ch;
    if (ch == '?')
    {
      int l, r;
      cin >> l >> r;
      if (l == r)
      {
        cout << 1 << '\n';
        continue;
      }
      cout << get(1, n - 1, 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 (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, 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, 1, r, r);
      }
    }
    else if (ch == '*')
    {
      int l, r;
      cin >> l >> r;
      st1.add(1, n, 1, l, r, inf);
      upd(1, n - 1, 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, 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, 1, r, r);
      }
    }
  }
}

Compilation message

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

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2140 KB Output is correct
3 Correct 10 ms 2140 KB Output is correct
4 Correct 12 ms 2216 KB Output is correct
5 Correct 9 ms 2156 KB Output is correct
6 Runtime error 456 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 971 ms 104628 KB Output is correct
2 Correct 56 ms 2644 KB Output is correct
3 Correct 802 ms 107708 KB Output is correct
4 Correct 920 ms 107724 KB Output is correct
5 Correct 801 ms 107600 KB Output is correct
6 Correct 852 ms 107640 KB Output is correct
7 Correct 932 ms 104532 KB Output is correct
8 Correct 937 ms 107040 KB Output is correct
9 Correct 883 ms 107068 KB Output is correct
10 Correct 688 ms 107188 KB Output is correct
11 Correct 845 ms 107092 KB Output is correct
12 Correct 894 ms 107232 KB Output is correct
13 Correct 482 ms 99412 KB Output is correct
14 Correct 510 ms 99208 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2140 KB Output is correct
3 Correct 10 ms 2140 KB Output is correct
4 Correct 12 ms 2216 KB Output is correct
5 Correct 9 ms 2156 KB Output is correct
6 Runtime error 456 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2140 KB Output is correct
3 Correct 10 ms 2140 KB Output is correct
4 Correct 12 ms 2216 KB Output is correct
5 Correct 9 ms 2156 KB Output is correct
6 Runtime error 456 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -