oj.uz

Submission #1003586

# Submission time Handle Problem Language Result Execution time Memory
1003586 2024-06-20T13:22:28 Z vjudge1 ZIGZAG (INOI20_zigzag) C++17
100 / 100
 1080 ms 108116 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)
  {
    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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2104 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 8 ms 2140 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 2040 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 104528 KB Output is correct
2 Correct 47 ms 2656 KB Output is correct
3 Correct 832 ms 107688 KB Output is correct
4 Correct 976 ms 107716 KB Output is correct
5 Correct 840 ms 107856 KB Output is correct
6 Correct 850 ms 107768 KB Output is correct
7 Correct 924 ms 104724 KB Output is correct
8 Correct 913 ms 107904 KB Output is correct
9 Correct 805 ms 107768 KB Output is correct
10 Correct 671 ms 107704 KB Output is correct
11 Correct 833 ms 107916 KB Output is correct
12 Correct 974 ms 108016 KB Output is correct
13 Correct 566 ms 99664 KB Output is correct
14 Correct 563 ms 99920 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2104 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 8 ms 2140 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 2040 KB Output is correct
8 Correct 296 ms 29616 KB Output is correct
9 Correct 330 ms 29580 KB Output is correct
10 Correct 301 ms 30580 KB Output is correct
11 Correct 179 ms 28244 KB Output is correct
12 Correct 314 ms 30780 KB Output is correct
13 Correct 290 ms 30660 KB Output is correct
14 Correct 271 ms 30816 KB Output is correct
15 Correct 381 ms 29556 KB Output is correct
16 Correct 293 ms 30548 KB Output is correct
17 Correct 267 ms 30632 KB Output is correct
18 Correct 155 ms 28500 KB Output is correct
19 Correct 167 ms 28536 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2136 KB Output is correct
2 Correct 9 ms 2104 KB Output is correct
3 Correct 10 ms 2012 KB Output is correct
4 Correct 8 ms 2140 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 2040 KB Output is correct
8 Correct 985 ms 104528 KB Output is correct
9 Correct 47 ms 2656 KB Output is correct
10 Correct 832 ms 107688 KB Output is correct
11 Correct 976 ms 107716 KB Output is correct
12 Correct 840 ms 107856 KB Output is correct
13 Correct 850 ms 107768 KB Output is correct
14 Correct 924 ms 104724 KB Output is correct
15 Correct 913 ms 107904 KB Output is correct
16 Correct 805 ms 107768 KB Output is correct
17 Correct 671 ms 107704 KB Output is correct
18 Correct 833 ms 107916 KB Output is correct
19 Correct 974 ms 108016 KB Output is correct
20 Correct 566 ms 99664 KB Output is correct
21 Correct 563 ms 99920 KB Output is correct
22 Correct 296 ms 29616 KB Output is correct
23 Correct 330 ms 29580 KB Output is correct
24 Correct 301 ms 30580 KB Output is correct
25 Correct 179 ms 28244 KB Output is correct
26 Correct 314 ms 30780 KB Output is correct
27 Correct 290 ms 30660 KB Output is correct
28 Correct 271 ms 30816 KB Output is correct
29 Correct 381 ms 29556 KB Output is correct
30 Correct 293 ms 30548 KB Output is correct
31 Correct 267 ms 30632 KB Output is correct
32 Correct 155 ms 28500 KB Output is correct
33 Correct 167 ms 28536 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1022 ms 105064 KB Output is correct
37 Correct 1050 ms 108112 KB Output is correct
38 Correct 573 ms 98900 KB Output is correct
39 Correct 1080 ms 108112 KB Output is correct
40 Correct 988 ms 105132 KB Output is correct
41 Correct 851 ms 108088 KB Output is correct
42 Correct 914 ms 105044 KB Output is correct
43 Correct 1012 ms 108024 KB Output is correct
44 Correct 934 ms 108116 KB Output is correct
45 Correct 1022 ms 108048 KB Output is correct
46 Correct 933 ms 108024 KB Output is correct
47 Correct 607 ms 100088 KB Output is correct