oj.uz

Submission #38224

# Submission time Handle Problem Language Result Execution time Memory
38224 2018-01-03T04:52:09 Z mirbek01 Money (IZhO17_money) C++14
0 / 100
 0 ms 21548 KB 
# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;

typedef long long ll;

int n, a[N], t[N * 4], ans = 1;

void update(int pos, int v = 1, int tl = 1, int tr = n){
      if(tl == tr)
            t[v] ++;
      else{
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  update(pos, v << 1, tl, tm);
            else
                  update(pos, (v << 1) | 1, tm + 1, tr);
            t[v] = t[v << 1] + t[(v << 1) | 1];
      }
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n){
      if(l > tr || tl > r) return 0;
      if(l <= tl && tr <= r) return t[v];
      int tm = (tl + tr) >> 1;
      return get(l, r, v << 1, tl, tm) +
                  get(l, r, (v << 1) | 1, tm + 1, tr);
}

int main(){
      scanf("%d", &n);

      for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);

      int f = 1;

      for(int i = 1; i <= n; i ++){
            if(a[i] < a[i - 1]){
                  ans ++;
                  while(f + 1 <= i)
                        update(a[f ++]);
            }
            else {
                  int sum = get(a[f + 1] + 1, a[i] - 1);
                  if(sum){
                        ans ++;
                        while(f + 1 < i)
                              update(a[f ++]);
                  }
            }
      }

      cout << ans << endl;
}

Compilation message

money.cpp: In function 'int main()':
money.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
                      ^
money.cpp:43:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
                               ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21548 KB Output is correct
2 Incorrect 0 ms 21548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21548 KB Output is correct
2 Incorrect 0 ms 21548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21548 KB Output is correct
2 Incorrect 0 ms 21548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21548 KB Output is correct
2 Incorrect 0 ms 21548 KB Output isn't correct
3 Halted 0 ms 0 KB -