Submission #1003403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003403		vjudge1	ZIGZAG (INOI20_zigzag)	C++17	8 / 100	2061 ms	21340 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
  int Lval, Rval;
  int Ld=0, Li=0, Rd=0,Ri=0;
  long long ans=0;
  int sz=0;
  node(){}
  node(int val) {
    sz=Ld=Li=Rd=Ri=1;
    ans=1;
    Lval=Rval=val;
  }
};
node merge(node L, node R) {
  node res;
  res.Lval = L.Lval;
  res.Rval = R.Rval;
  res.sz = L.sz+R.sz;
  res.Ld = L.Ld;
  res.Li = L.Li;
  res.Rd = R.Rd;
  res.Ri = R.Ri;
  res.ans = L.ans+R.ans;
  if(L.Rval > R.Lval) {
    res.ans -= L.Rd*(L.Rd+1)/2;
    res.ans -= R.Li*(R.Li+1)/2;
    long long sz = L.Rd + R.Li;
    res.ans += sz*(sz+1)/2;
    if(R.sz == R.Li) {
      if(R.sz%2 == 1) {
        res.Ri = sz;
      }
      else {
        res.Rd = sz;
      }
    }
    if(L.sz == L.Rd) {
      if(L.sz%2 == 1) {
        res.Ld = sz;
      }
      else {
        res.Li = sz;
      }
    }
  }
  else if(L.Rval < R.Lval) {
    res.ans -= L.Ri*(L.Ri+1)/2;
    res.ans -= R.Ld*(R.Ld+1)/2;
    long long sz = L.Ri + R.Ld;
    res.ans += sz*(sz+1)/2;
    if(R.sz == R.Ld) {
      if(R.sz%2 == 1) {
        res.Rd = sz;
      }
      else {
        res.Ri = sz;
      }
    }
    if(L.sz == L.Ri) {
      if(L.sz%2 == 1) {
        res.Li = sz;
      }
      else {
        res.Ld = sz;
      }
    }
  }
  return res;
}

signed main () {
  int n,q;
  cin >> n >> q;
  node a[n];
  int A[n];
  for(int i =0 ;i<n;i++) {
    cin >>  A[i];
    a[i]=node(A[i]);
  }
  while(q--) {
    char c;
    cin >> c;
    if(c=='?'){ 
      int l, r;
      cin >> l >> r;
      l--,r--;
      node res = a[l];
//      cout << l << " " << l << " Ld "  << res.Ld << " Li " << res.Li << " Rd " << res.Rd << " Ri " << res.Ri << " ans " << res.ans << endl;
      for(int i = l+1;i<=r;i++) {
        res = merge(res, a[i]);
//      cout << l << " " << l << " Ld "  << res.Ld << " Li " << res.Li << " Rd " << res.Rd << " Ri " << res.Ri << " ans " << res.ans << endl;
      }
      cout << res.ans << "\n";
    }
    else if(c == '*') {
      int l, r;
      cin >> l >> r;
      l--,r--;
      for(int i = l;i<=r;i++) {
        A[i]*=-1;
        a[i] = node(A[i]);
      }
    }
    else if(c == '+') {
      int l, r, val;
      cin >> l >> r >> val;
      l--,r--;
      for(int i = l;i<=r;i++) {
        A[i]+=val;
        a[i] = node(A[i]);
      }
    }
  }
}

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