Submission #1055325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055325		YassirSalama	Financial Report (JOI21_financial)	C++17	5 / 100	442 ms	47384 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
const int maxn=3e5+100;
#define all(v) v.begin(),v.end()
struct Node{
    int val;
    Node* left,*right;
    Node() : left(nullptr),right(nullptr){}
};
void update(Node* node,int l,int r,int ql,int x){
    if(l==r){
        node->val=max(node->val,x);
        return;
    }
    int mid=(l+r)>>1;
    if(ql<=mid){
        if(node->left==nullptr) node->left=new Node();
        update(node->left,l,mid,ql,x);
    }else{
        if(node->right==nullptr) node->right=new Node();
        update(node->right,mid+1,r,ql,x);
    }
    int c=0;
    if(node->left) c=max(node->left->val,c);
    if(node->right) c=max(node->right->val,c);
    node->val=c;
}
int query(Node* node,int l,int r,int ql,int qr){
    if(ql>qr) return 0;
    if(!node) return 0;
    if(ql<=l&&r<=qr) return node->val;
    int mid=(l+r)/2;
    int ans=0;
    if(ql<=mid) ans=max(ans,query(node->left,l,mid,ql,qr));
    if(qr>mid) ans=max(ans,query(node->right,mid+1,r,ql,qr));
    return ans;
}
signed main(){
    Node* root=new Node();
    int n,d;
    cin>>n>>d;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int> c=v;c.insert(c.begin(),-1);sort(all(c));c.erase(unique(all(c)),c.end());
    map<int,int> mp;for(int i=0;i<c.size();i++) mp[c[i]]=i;
    int ans=0;
    for(int i=0;i<n;i++){
        int x=query(root,0,c.size()-1,0,mp[v[i]]-1);
        x++;
        ans=max(ans,x);
        update(root,0,c.size()-1,mp[v[i]],x);
    }
    cout<<ans<<endl;

}

Compilation message (stderr)

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

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35