oj.uz

Submission #480139

# Submission time Handle Problem Language Result Execution time Memory
480139 2021-10-14T19:58:44 Z lukameladze Po (COCI21_po) C++14
70 / 70
 20 ms 7380 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 1e5 + 5;
int n,a[N],ff,nxt,ans,cur,le,sf[N];
vector <int> v[N];
set <int > s;
signed main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n;
     for (int i = 1; i <= n ;i++) {
          cin>>a[i];
     }
     for (int i = n; i >= 1; i --) {
          cur = i + 1;
          while (cur != n + 1 && a[cur] >= a[i]) {
               cur = sf[cur];
          }
          sf[i] = cur;
     }
     cur = 0;
     for (int i = 1; i <= n; i++) {
          for (int j = 0; j < v[i].size(); j++) {
               cur -= v[i][j];
          }
          a[i] -= cur;
          if (a[i]) ans++;
          nxt = sf[i];
          cur += a[i];
          v[nxt].pb(a[i]);
     }
     cout<<ans<<endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:25:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |           for (int j = 0; j < v[i].size(); j++) {
      |                           ~~^~~~~~~~~~~~~

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2552 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 8 ms 3788 KB Output is correct
5 Correct 12 ms 4428 KB Output is correct
6 Correct 20 ms 5788 KB Output is correct
7 Correct 17 ms 7380 KB Output is correct