Submission #1158982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158982		akamizane	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	19 ms	47328 KiB

Main

#include<bits/stdc++.h>
 
using namespace std;

#define debug(...) 40

using ll = long long;
using pii = pair<int,int>;

#define int long long
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, a, n) for (int i = (a); i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}

void setIO(string s) {
  // freopen((s + ".inp").c_str(), "r", stdin);
  // freopen((s + ".out").c_str(), "w", stdout);
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;

struct Node{
   int border[2] = {};
   int dp[2][2] = {};
   Node(){}
   Node(int v){
      border[0] = border[1] = v;
      dp[0][1] = dp[1][0] = dp[0][0] = 0;
      dp[1][1] = v;
   }
};

Node operator + (Node x, Node y){
   Node ans;
   ans.border[0] = x.border[0];
   ans.border[1] = y.border[1];
   for (int l = 0; l < 2; l++){
      for (int m = 0; m < 2; m++){
         for (int o = 0; o < 2; o++){
            for (int r = 0; r < 2; r++){
               if (m && o){
                  if ((x.border[1] < 0) == (y.border[0] < 0) ){
                     chmax(ans.dp[l][r], x.dp[l][m] + y.dp[o][r]);
                  }
               }
               else{
                  chmax(ans.dp[l][r], x.dp[l][m] + y.dp[o][r]);
               }
            }
         }
      }
   }
   return ans; 
}

void up(Node& x, ll v){
   x.border[0] += v;
   x.border[1] += v;
   x.dp[1][1] = abs(x.border[0]);
}

Node t[maxn << 2];
Node b[maxn];

void build(int id, int l, int r){
   if (l == r){
      t[id] = b[l];
      return;
   }
   int m = (l + r) >> 1;
   build(id << 1, l, m);
   build(id << 1 | 1, m + 1, r);
   t[id] = t[id << 1] + t[id << 1 | 1];
}

void update(int id, int l, int r, int pos, int v){
   if (l == r){
      up(t[id], v);
      return;
   }
   int m = (l + r) >> 1;
   if (pos <= m) update(id << 1, l, m, pos, v);
   else update(id << 1 | 1, m + 1, r, pos, v);
   t[id] = t[id << 1] + t[id << 1 | 1];
}

Node get(int id, int l, int r, int u, int v){
   if (r < u || v < l) return Node();
   if (u <= l && r <= v) return t[id];
   int m = (l + r) / 2;
   return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u , v);
}

int32_t main() {
  // setIO("cowbasic");
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
   int n, q;
   cin >> n >> q;
   vector<int> a(n);
   for (auto& x : a) cin >> x;
   for (int i = 0; i < n - 1; i++){
      b[i] = a[i + 1] - a[i];
   }
   build(1, 0, n - 2);
   while(q--){
      int l, r, x;
      cin >> l >> r >> x;
      l--; r--;
      if (l - 1 >= 0) update(1, 0, n - 2, l - 1, x);
      if (r < n - 1) update(1, 0, n - 2, r + 1, -x);
      cout << t[1].dp[1][1] << "\n";
   }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55