Submission #46904

#	Time	Username	Problem	Language	Result	Execution time	Memory
46904		rajarshi_basu	Money (IZhO17_money)	C++14	0 / 100	2 ms	804 KiB

money

#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-1) != 0)) ctr++;
    update(node,0,(int)1e9+1,a,1);
    prev = a;
  }
  cout << ctr <<endl;


  return 0;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:62:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if(a<prev or a!=prev+1 and (get(node,0,(int)1e9 +1 , prev+1,a-1) != 0)) ctr++;
                  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55