oj.uz

Submission #46906

# Submission time Handle Problem Language Result Execution time Memory
46906 2018-04-24T16:27:11 Z rajarshi_basu Money (IZhO17_money) C++14
0 / 100
 2 ms 528 KB 
#include <iostream>
#include <algorithm>


#define FOR(i,n) for(int i=0;i<n;i++)
/*#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define pb(a) push_back(a)
#define vi vector<int>
#define ii pair<int,int>
#define iii pair<pair<int,int>, int>
#define mp(a,b) make_pair(a,b)
*/

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int val;
};

void expand(Node* node){
  if(node->left == NULL)node->left = new Node();
  if(node->right == NULL)node->right = new Node();
}
void update(Node* node,int ss,int se,int i ,int val){
  expand(node);
  if(ss > i or i>se)return;
  if(ss==se){
    node->val+=val;
    return;
  }
  int mid = (ss+se)/2;
  update(node->left,ss,mid,i,val);
  update(node->right,mid+1,se,i,val);
  node->val = node->left->val + node->right->val;

}
int get(Node* node,int ss,int se,int qs,int qe)
{ expand(node);
  if(ss>qe or se<qs)return 0;
  if(qs<=ss and se<=qe){
    return node->val;
  }
  int mid= (ss+se)/2;
  return get(node->left,ss,mid,qs,qe) + get(node->right,mid+1,se,qs,qe);

}

int main(){
  int n;
  cin >> n;
  int prev = 0;
  int ctr = 1;
  Node* node = new Node();
  FOR(i,n){
    int a;
    cin >> a;
    if(a==prev)continue;

    if(a<prev or ((a>prev+1) and (get(node,0,(int)1e9 +1 , prev+1,a) != 0)))ctr++;
    update(node,0,(int)1e9+1,a,1);
    prev = a;
  }
  cout << ctr <<endl;


  return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Incorrect 2 ms 528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Incorrect 2 ms 528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Incorrect 2 ms 528 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Incorrect 2 ms 528 KB Output isn't correct
9 Halted 0 ms 0 KB -