Submission #1153881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153881		justin271828	Po (COCI21_po)	C++20	30 / 70	1096 ms	14664 KiB

Main

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

const int INF = 1234567890;

vector<int> v;

struct node {
  int s, e, m, val, lazy;
  node *l, *r;
  node (int S, int E) :
    s(S), e(E), m((S+E)/2), val(0), lazy(0) {
      if (s != e) {
        l = new node(s, m);
        r = new node(m+1, e);
      }
    }
  void prop() {
    l->val += lazy;
    l->lazy += lazy;
    r->val += lazy;
    r->lazy += lazy;
    lazy = 0;
  }
  void up(int x, int y, int k) {
    if (x <= s && e <= y) {
      val += k;
      lazy += k;
      return;
    }
    else if (x > e || y < s) return;
    prop();
    l->up(x, y, k);
    r->up(x, y, k);
    //if (l->s == l->e && l->val == 0) v.push_back(l->s);
    //if (r->s == r->e && r->val == 0) v.push_back(r->s);
    val = min(l->val,  r->val);
  }
  int q(int x, int y) {
    if (x <= s && e <= y) return val;
    else if (x > e || y < s) return INF;
    prop();
    return min(l->q(x, y), r->q(x, y));
  }
  int bsta(int x) {
    if (s == e) {
      if (val == 0) return s;
      else return INF;
    }
    prop();
    if (x <= m && l->val == 0) {
      if (l->bsta(x) != INF) return l->bsta(x);
    }
    if (r->val == 0) {
      return r->bsta(x);
    }
    else return INF;
  }
}*tree;

int main() {
  int n;
  cin >> n;
  set<int> nz;
  tree = new node(0, n-1);
  int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    if (arr[i] != 0) {
        nz.insert(i);}
    tree->up(i, i, arr[i]);}
  set<int>::iterator it;
  int ans = 0;
  while (nz.begin() != nz.end()) {
    int temp = tree->bsta(*(nz.begin()));
    int temp2 = tree->q(*(nz.begin()), temp-1);
    tree->up(*(nz.begin()), temp-1, 0-temp2);
    ans++;
    for (int i = 0; i < n; i++) if (tree->q(i, i) == 0 && nz.find(i) != nz.end()) nz.erase(nz.find(i));
  }
  cout << ans;
  return 0;
}

• Subtask 1: 30 / 70