제출 #619991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619991		APROHACK	Financial Report (JOI21_financial)	C++14	100 / 100	880 ms	50276 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
ll n, a, d, maxans, curr;
vector<ll>arr, compressed;
struct financial
{
    int dd, ht, val, mid;
    bool hay;

    financial *L, *R;
    financial(){}
    financial(int l, int r){
        ////cout << l << " " << r << endl;
        dd = l, ht = r;
        mid = (dd+ht)/2;
        if(dd!=ht){
            L = new financial(l, mid);
            R = new financial(mid+1, r);
            val = max(L->val, R->val);
        }else{
            val = 0;
        }
        hay = false;
    }
    void propagate(){
        if(hay){
            L->erasing(dd, mid);
            R->erasing(mid+1, ht);
            val = max(L->val, R->val);
            hay = false;
        }
    }
    void push(int where, int value){
        if(dd==ht){
            //cout << where << " - > " << value << endl;
            val = value;
        }else{
            propagate();
            if(where<=mid){
                L->push(where , value);
            }else{
                R->push(where, value);
            }
            val = max(L->val, R->val);
        }
    }
    void erasing(int l, int r){
        if(l==dd && r == ht){
            //cout << "upd 0 " << l << " " << r << endl;
            val = 0;
            hay = true;
        }else{
            //cout<<"in " << dd << " " << ht << " " << l << " " << r << endl; 
            if(r<=mid){
                L->erasing(l, r);
            }else if(l>mid){
                R->erasing(l, r);
            }else{
                L->erasing(l, mid);
                R->erasing(mid+1, r);
            }
            val = max(L->val, R->val);
        }
    }
    int query(int l, int r){
        if(l==dd && r == ht){
            //cout << "ans "<<l << " " << r << " " << val << endl;
            return val;
        }else{
            //cout<<"asking in " << dd << " " << ht << " " << l << " " << r << endl; 
            propagate();
            if(r<=mid){
                return L->query(l, r);
            }else if(l>mid){
                return R->query(l, r);
            }else {
                ll kkkk = L->query(l, mid);
                ll pppp = R->query(mid+1, r);
                return max(kkkk, pppp);
            }
        }
    }
};

void input(){
    //freopen("input.txt", "r", stdin);
    cin>>n>>d;
    for(int i = 0 ; i < n; i ++){
        cin>>a;
        arr.pb(a);
        compressed.pb(a);
    }
    map<int, int>mp;
    sort(arr.begin(), arr.end());
    curr = 0;
    for(int i = 0 ;i < n ; i++){
        mp[arr[i]]=curr++;
    }
    for(int i = 0 ; i < n ; i ++){
        compressed[i]=mp[compressed[i]];
        //cout << compressed[i] << " ";
    }
    //cout << endl;
}
financial *st;
void calculate(){
    st = new financial(0, curr);
    ll currentAns = 1, minimum;
    multiset<int>nextD;
    for(int i = n-1 ; i>= 0; i --){
        if(nextD.size()==d){
            for(auto temp:nextD){
                minimum=temp;
                break;
            }
            if(minimum>=1)st->erasing(0, minimum-1);
            nextD.erase(nextD.find(compressed[i+d]));
        }
        currentAns = 1 + st->query(compressed[i]+1, curr);
        maxans = max(maxans, currentAns);
        nextD.insert(compressed[i]);
        st->push(compressed[i], currentAns);
    }
}
int main(){
    input();
    maxans=1;
    calculate();
    cout << maxans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void calculate()':
Main.cpp:115:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  115 |         if(nextD.size()==d){
      |            ~~~~~~~~~~~~^~~
Main.cpp:120:49: warning: 'minimum' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |             if(minimum>=1)st->erasing(0, minimum-1);
      |                                          ~~~~~~~^~

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