oj.uz

Submission #928597

# Submission time Handle Problem Language Result Execution time Memory
928597 2024-02-16T17:42:33 Z ind1v Bigger segments (IZhO19_segments) C++11
0 / 100
 1 ms 2520 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

struct point_t {
  long long x, y;
  
  point_t() {}
  
  point_t(long long _x, long long _y) : x(_x), y(_y) {}
};

struct vector_t {
  long long x, y;
  
  vector_t() {}
  
  vector_t(point_t a, point_t b) : x(b.x - a.x), y(b.y - a.y) {}
  
  long long cross(vector_t o) {
    return x * o.y - y * o.x;
  }
};

bool cw(point_t a, point_t b, point_t c) {
  vector_t ab(a, b), ac(a, c);
  return ab.cross(ac) < 0;
}

int n;
int a[N];
point_t p[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  long long s = 0;
  p[0] = point_t(0, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    s += a[i];
    p[i] = point_t(i, s);
  }
  vector<point_t> v;
  v.push_back(p[0]);
  v.push_back(p[1]);
  for (int i = 2; i <= n; i++) {
    while ((int) v.size() >= 2 && cw(v[(int) v.size() - 2], v.back(), p[i])) {
      v.pop_back();
    }
    v.push_back(p[i]);
  }
  cout << (int) v.size() - 1 << '\n';
  return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -