oj.uz

Submission #1003403

# Submission time Handle Problem Language Result Execution time Memory
1003403 2024-06-20T09:48:17 Z vjudge1 ZIGZAG (INOI20_zigzag) C++17
8 / 100
 2000 ms 21340 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 600 KB Output is correct
2 Correct 47 ms 604 KB Output is correct
3 Correct 55 ms 860 KB Output is correct
4 Correct 55 ms 860 KB Output is correct
5 Correct 49 ms 860 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 160 ms 860 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 21340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 600 KB Output is correct
2 Correct 47 ms 604 KB Output is correct
3 Correct 55 ms 860 KB Output is correct
4 Correct 55 ms 860 KB Output is correct
5 Correct 49 ms 860 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 160 ms 860 KB Output is correct
8 Execution timed out 2033 ms 7952 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 600 KB Output is correct
2 Correct 47 ms 604 KB Output is correct
3 Correct 55 ms 860 KB Output is correct
4 Correct 55 ms 860 KB Output is correct
5 Correct 49 ms 860 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 160 ms 860 KB Output is correct
8 Execution timed out 2061 ms 21340 KB Time limit exceeded
9 Halted 0 ms 0 KB -