oj.uz

답안 #1003579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1003579 2024-06-20T13:16:46 Z vjudge1 ZIGZAG (INOI20_zigzag) C++17
42 / 100
 1054 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;
      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:197:7: warning: unused variable 'f' [-Wunused-variable]
  197 |   int f = 1;
      |       ^

Subtask #1
0 / 8.0

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

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1054 ms 104660 KB Output is correct
2 Correct 41 ms 6740 KB Output is correct
3 Correct 816 ms 107804 KB Output is correct
4 Correct 943 ms 107856 KB Output is correct
5 Correct 834 ms 107860 KB Output is correct
6 Correct 912 ms 107860 KB Output is correct
7 Correct 944 ms 104776 KB Output is correct
8 Correct 965 ms 107860 KB Output is correct
9 Correct 834 ms 107860 KB Output is correct
10 Correct 649 ms 107724 KB Output is correct
11 Correct 743 ms 107704 KB Output is correct
12 Correct 859 ms 107784 KB Output is correct
13 Correct 527 ms 99528 KB Output is correct
14 Correct 490 ms 99580 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2140 KB Output is correct
2 Correct 9 ms 2208 KB Output is correct
3 Correct 10 ms 2136 KB Output is correct
4 Correct 10 ms 2140 KB Output is correct
5 Correct 9 ms 2140 KB Output is correct
6 Runtime error 495 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 2140 KB Output is correct
2 Correct 9 ms 2208 KB Output is correct
3 Correct 10 ms 2136 KB Output is correct
4 Correct 10 ms 2140 KB Output is correct
5 Correct 9 ms 2140 KB Output is correct
6 Runtime error 495 ms 1048576 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -